CSES - HIIT Open 2018 - Results
Submission details
Task:Euclidean Geometry
Sender:barely div 2.8 burgeria
Submission time:2018-05-26 14:13:44
Language:C++
Status:READY
Result:
Test results
testverdicttime
#10.05 sdetails
#20.05 sdetails
#30.04 sdetails
#40.05 sdetails
#50.03 sdetails
#60.04 sdetails
#70.06 sdetails
#80.04 sdetails

Compiler report

input/code.cpp: In function 'int limitChanges(std::vector<double>&, double)':
input/code.cpp:57:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < v.size(); i++) {
                  ~~^~~~~~~~~~
input/code.cpp:58:12: warning: suggest parentheses around comparison in operand of '!=' [-Wparentheses]
   if (v[i] < limit != v[i-1] < limit) {
input/code.cpp: In function 'std::vector<std::pair<int, int> > asd(std::vector<std::__cxx11::basic_string<char> >&)':
input/code.cpp:93:9: warning: unused variable 'totsSum' [-Wunused-variable]
  double totsSum = 0;
         ^~~~~~~
input/code.cpp:111:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

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';
}



void sorttaa(vector<pair<int,int>> & v) {
	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,b};
}



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++;
		}
	}
	return limitChanges;
}

vector<pair<int,int>> asd(vector<string> & v) {
	int row = 0; int col = 0;
	vector<pair<int,int>> ans;
	vector<int> dr {1, -1, 0, 0};
	vector<int> dc {0, 0, 1, -1};
	for (; row < 100; row++) {
		for (; col < 100; col++) {
			for (int asd = 0; asd < 4; asd++) {
				if (v[row][col] == '1' && !iszero(v, row + dr[asd], col + dc[asd])) {
					ans.emplace_back(row, col);
					break;
				}
			}
		}
	}
	sorttaa(ans);
	
	vector<pair<double, double>> mav;
	int sz = ans.size();
	for (int i = 0; i < sz; i++) {
		int end = (i + 7) % sz;
		mav.emplace_back(ans[end].first - ans[i].first, ans[end].second - ans[i].first);
	}
	
	// moi jnalanko
	vector<pair<double, double>> avg;
	
	vector<double> tots;
	double totsSum = 0;
	for (int i = 0; i < sz; i++) {
		avg.emplace_back(getavg(mav, i));
		tots.emplace_back(avg.back().first + avg.back().second);
	}

	double limit = 0.001;
	int threes = 0;
	int fours = 0;
	for (int qq = 0; qq < 10000; qq++) {
		int ls = limitChanges(tots, limit);
		if (ls == 6) threes++;
		if (ls == 8) fours++;
		limit += 0.001;
	}
	if (threes > fours) cout << 3;
	else 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.emplace_back(s);
	}
	asd(v);
	}

	

}

Test details

Test 1

Verdict:

input
100
000000000000000000000000000000...

correct output
3
3
3
3
4
...

user output
4
4
4
4
4
...

Test 2

Verdict:

input
100
000000000000000000000000000000...

correct output
3
4
4
4
3
...

user output
4
4
4
4
4
...

Test 3

Verdict:

input
100
000000000000000000000000000000...

correct output
3
3
3
3
4
...

user output
4
4
4
4
4
...

Test 4

Verdict:

input
100
000000000000000000000000000000...

correct output
3
3
3
4
3
...

user output
4
4
4
4
4
...

Test 5

Verdict:

input
100
000000000000000000000000000000...

correct output
3
4
3
3
4
...

user output
4
4
4
4
4
...

Test 6

Verdict:

input
100
000000000000000000000000000000...

correct output
4
3
4
4
4
...

user output
4
4
4
4
4
...

Test 7

Verdict:

input
100
000000000000000000000000000000...

correct output
4
4
3
3
3
...

user output
4
4
4
4
4
...

Test 8

Verdict:

input
100
000000000000000000000000000000...

correct output
3
3
3
3
3
...

user output
4
4
4
4
4
...