CSES - HIIT Open 2018 - Results
Submission details
Task:Euclidean Geometry
Sender:barely div 2.8 burgeria
Submission time:2018-05-26 15:58:07 +0300
Language:C++
Status:READY
Result:
Test results
testverdicttime
#10.07 sdetails
#20.06 sdetails
#30.08 sdetails
#40.07 sdetails
#50.03 sdetails
#60.06 sdetails
#70.07 sdetails
#80.07 sdetails

Compiler report

input/code.cpp: In function 'int limitChanges(std::vector<double>&, double)':
input/code.cpp:74:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < v.size(); i++) {
                  ~~^~~~~~~~~~
input/code.cpp: In function 'void asd(std::vector<std::__cxx11::basic_string<char> >&)':
input/code.cpp:146:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < mav.size(); i++) {
                  ~~^~~~~~~~~~~~

Code

#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <utility>
#include <algorithm>

using namespace std;

typedef long long LL;




bool iszero(vector<string> & v, int row, int col) {
	if (row < 0 || col < 0 || row >= 100 || col >= 100) return true;
	return v[row][col] == '0';
}


/*
bool isNb(int r1, int c1, int r2, int c2) {
	if (abs(r2-r1) <= 1 && abs(c1-c2) <= 1) return true;
	return false;
}
vector<pair<int,int>> sorttaa(vector<pair<int,int>> & v) {
	int row, int col;
	row = v[0].first;
	col = v[0].second;
	vector<pair<int,int>> ans {{row, col}};
	set<pair<int,int>> seen{{row, col}};
	for (auto p : v) {
		if (isNb(ans.back().first, ans.back().second, p.first, p.second) && seen.count(p) == 0) {
			seen.insert(p);
			ans.push_back(p);
		}
	}
	return ans;
	
	sort(v.begin(), v.end(), [](pair<int,int> left, pair<int,int> right) {
		if (left.second != right.second) return left.second > right.second;
		return left.first < right.first;
	});
}
*/
pair<double, double> getavg(vector<pair<double, double>> & v, int idx) {
	int sz = v.size();
	double eka = 0;
	double toka = 0;
	double tot = 0;
	for (int i = idx - 3; i < idx + 3; i++) {
		int ac = (i + sz) % sz;
		eka += v[ac].first;
		toka += v[ac].second;
		tot += 1;
	}
	eka /= tot;
	toka /= tot;
	double a = 0;
	double b = 0;
	for (int i = idx - 3; i < idx + 3; i++) {
		int ac = (i + sz) % sz;
		a += (v[ac].first - eka)*(v[ac].first - eka);
		b += (v[ac].second - toka)*(v[ac].second - toka);
	}
	return {a/tot,b/tot};
}



int limitChanges(vector<double> & v, double limit) {
	int limitChanges = 0;
	for (int i = 1; i < v.size(); i++) {
		if ((v[i] < limit) != (v[i-1] < limit)) {
			limitChanges++;
		}
	}
	if ((v[0] < limit) != (v.back() < limit)) limitChanges++;
	return limitChanges;
}

bool isedge(vector<string> & v, int row, int col) {
	vector<int> dr {1, -1, 0, 0};
	vector<int> dc {0, 0, 1, -1};
	for (int asd = 0; asd < 4; asd++) {
		if (v[row][col] == '1' && iszero(v, row + dr[asd], col + dc[asd])) {
			return true;
		}
	}
	return false;

}

void asd(vector<string> & v) {
	int row = 0; int col = 0;
	for (; row < 100; row++) {
		for (col=0; col < 100; col++) {
			if (v[row][col] != '0') goto mansplaining;
		}
	}
	mansplaining:
	
//cout << v[0][0] << " ";
//cout << row << "| " <<col <<endl;
	
	vector<int> dr8 {-1, -1, 0, 1, 1, 1, 0, -1};
	vector<int> dc8 {0, 1, 1, 1, 0, -1, -1, -1};
	set<pair<int,int>> seen{{row, col}};
	vector<pair<int,int>> ans{{row, col}};
	while (true) {
	bool brek = true;
	for (int ff = 0; ff < 8; ff++) {
		int candr = row + dr8[ff];
		int candc = col + dc8[ff];
		if (candr < 0 || candr >= 100 || candc < 0 || candc >= 100) continue;
//cout << row << " " << col << " " << candr << " " << candc << endl;
		if (isedge(v, candr, candc) && !seen.count({candr, candc})) {
			row = candr;
			col = candc;
			seen.emplace(row, col);
			ans.emplace_back(row, col);
			brek = false;
			break;
		}
	}
	if (brek) break;
	}
	
	
	vector<pair<double, double>> mav;
	int sz = ans.size();
//cout << sz<<endl;
	for (int i = 0; i < sz; i++) {
		int end = (i + 7) % sz;
		double h = ans[end].first - ans[i].first;
		double k = ans[end].second - ans[i].second;
		if (h*h + k*k > 25)
		mav.emplace_back(h,k);
	}
	
	// moi jnalanko
	vector<pair<double, double>> avg;
	
	vector<double> tots;
	for (int i = 0; i < mav.size(); i++) {
		avg.emplace_back(getavg(mav, i));
		tots.emplace_back(avg.back().first + avg.back().second);
	}

	double limit = 0.0001;
	int threes = 0;
	int fours = 0;
//cout << tots.size() << endl;
//for (auto gg : tots) cout << gg << " ";
	double inc = 0.0001;
	bool nonzeroseen = false;
	while (true) {

		int ls = limitChanges(tots, limit);
		if (ls > 0) nonzeroseen = true;
//cout << ls << endl;
		if (ls == 0 && nonzeroseen) break;
		if (ls == 6) threes++;
		if (ls == 8) fours++;
		limit += inc;
		inc *= 1.15;
	}
//cout << threes << " " << fours << endl;
	if (threes > fours) cout << 3;
	else if (fours >= threes)cout << 4;
	cout <<endl;
}


int main() {
/*
	vector<pair<int,int>> test {{2,5},{1,5},{3,3}};
	sorttaa(test);
	for (auto a : test) cout << a.first << " " << a.second << endl;
	return 0;
*/
	int t; cin >> t;
	while (t--) {
	vector<string> v;
	for (int i = 0; i < 100; i++) {
		string s; cin>>s;
		v.push_back(s);
	}
	asd(v);
	}

	

}

Test details

Test 1

Verdict:

input
100
000000000000000000000000000000...

correct output
3
3
3
3
4
...

user output
3
3
3
3
4
...

Test 2

Verdict:

input
100
000000000000000000000000000000...

correct output
3
4
4
4
3
...

user output
3
4
4
4
3
...

Test 3

Verdict:

input
100
000000000000000000000000000000...

correct output
3
3
3
3
4
...

user output
4
3
3
3
4
...

Test 4

Verdict:

input
100
000000000000000000000000000000...

correct output
3
3
3
4
3
...

user output
3
3
4
4
3
...

Test 5

Verdict:

input
100
000000000000000000000000000000...

correct output
3
4
3
3
4
...

user output
3
4
3
3
4
...

Test 6

Verdict:

input
100
000000000000000000000000000000...

correct output
4
3
4
4
4
...

user output
4
3
4
4
3
...

Test 7

Verdict:

input
100
000000000000000000000000000000...

correct output
4
4
3
3
3
...

user output
4
4
3
3
3
...

Test 8

Verdict:

input
100
000000000000000000000000000000...

correct output
3
3
3
3
3
...

user output
3
3
3
3
3
...