Submission #120313

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
120313	2019-06-24T07:23:10 Z	tmwilliamlin168	Printed Circuit Board (CEOI12_circuit)	C++14	85 / 100	52 ms	11120 KB

circuit

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int mxN=2e5;
int n, l, r;
ll x[mxN], y[mxN];
vector<int> v, s;
bool b[mxN];

ll cp(int a, int b, int c) {
	return (y[c]-y[a])*(x[b]-x[a])-(y[b]-y[a])*(x[c]-x[a]);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	for(int i=0; i<n; ++i) {
		cin >> x[i] >> y[i];
		if(!i||cp(n, l, i)>0||!cp(n, l, i)&&x[i]<x[l])
			l=i;
		if(!i||cp(n, r, i)<0||!cp(n, r, i)&&x[i]<x[r])
			r=i;
	}
	//cout << l << " " << r << endl;
	int ic=cp((l+n-1)%n, l, (l+1)%n)>0?1:n-1;
	for(; l^r; l=(l+ic)%n)
		v.push_back(l);
	v.push_back(r);
	//cout << "a" << endl;
	//for(int i : v)
		//cout << x[i] << " " << y[i] << endl;
	s={0, 1};
	for(int i=2; i<v.size(); ++i) {
		//cout << i << endl;
		//for(int si : s)
			//cout << si << " ";
		//cout << endl;
		//0 cases
		//sttraight line all 0s?
		if(cp(n, v[i-1], v[i])<0) {
			if(cp(n, v[i-2], v[i-1])>0&&cp(v[i-2], v[i-1], v[i])<0) {
				while(cp(n, v[s.back()], v[i])<=0)
					++i;
				s.pop_back();
				while(cp(n, v[s.back()], v[i])>=0&&cp(v[i-1], v[i], v[s.back()])<0)
					s.pop_back();
				if(cp(n, v[s.back()], v[i])>=0) {
					int j=i, c=0;
					while(cp(n, v[s.back()], v[i])>=0||!c) {
						if(i==j)
							c+=cp(n, v[i], v[i+1])<0&&cp(v[i-1], v[i], v[i+1])>0;
						if(cp(n, v[j], v[i])>=0&&cp(n, v[j], v[i+1])<0&&cp(v[i], v[i+1], v[j])>0)
							++c;
						if(cp(n, v[j], v[i])<0&&cp(n, v[j], v[i+1])>=0&&cp(v[i], v[i+1], v[j])<0)
							--c;
						++i;
					}
				}
			} else if(!cp(n, v[i-1], v[i]))
				s.pop_back();
		} else if(cp(n, v[i-1], v[i])>0) {
			if(cp(n, v[i-2], v[i-1])<0&&cp(v[i-2], v[i-1], v[i])>0) {
				while(cp(n, v[s.back()], v[i])>=0)
					++i;
			} else {
				//note <= here so we can pop off v[i-1]
				while(cp(n, v[s.back()], v[i])>=0&&cp(v[i-1], v[i], v[s.back()])<=0)
					s.pop_back();
				if(cp(n, v[s.back()], v[i])>=0) {
					int j=i, c=0;
					while(cp(n, v[s.back()], v[i])>=0||!c) {
						if(i==j)
							c+=cp(n, v[i], v[i+1])<0&&cp(v[i-1], v[i], v[i+1])>0;
						if(cp(n, v[j], v[i])>=0&&cp(n, v[j], v[i+1])<0&&cp(v[i], v[i+1], v[j])>0)
							++c;
						if(cp(n, v[j], v[i])<0&&cp(n, v[j], v[i+1])>=0&&cp(v[i], v[i+1], v[j])<0)
							--c;
						++i;
					}
				}
			}
		} else {
			if((cp(n, v[i-2], v[i-1])<0)==(cp(v[i-2], v[i-1], v[i])<0))
				s.pop_back();
			else if(cp(n, v[i-2], v[i-1])<0) {
				while(cp(n, v[s.back()], v[i])>=0)
					++i;
			} else {
				while(cp(n, v[s.back()], v[i])<=0)
					++i;
				s.pop_back();
				while(cp(n, v[s.back()], v[i])>=0&&cp(v[i-1], v[i], v[s.back()])<0)
					s.pop_back();
				if(cp(n, v[s.back()], v[i])>=0) {
					int j=i, c=0;
					while(cp(n, v[s.back()], v[i])>=0||!c) {
						if(i==j)
							c+=cp(n, v[i], v[i+1])<0&&cp(v[i-1], v[i], v[i+1])>0;
						if(cp(n, v[j], v[i])>=0&&cp(n, v[j], v[i+1])<0&&cp(v[i], v[i+1], v[j])>0)
							++c;
						if(cp(n, v[j], v[i])<0&&cp(n, v[j], v[i+1])>=0&&cp(v[i], v[i+1], v[j])<0)
							--c;
						++i;
					}
				}
			}
		}
		s.push_back(i);
	}
	cout << s.size() << "\n";
	for(int a : s)
		b[v[a]]=1;
	for(int i=0; i<n; ++i)
		if(b[i])
			cout << i+1 << " ";
}

Compilation message

circuit.cpp: In function 'int main()':
circuit.cpp:23:37: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   if(!i||cp(n, l, i)>0||!cp(n, l, i)&&x[i]<x[l])
                         ~~~~~~~~~~~~^~~~~~~~~~~
circuit.cpp:25:37: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   if(!i||cp(n, r, i)<0||!cp(n, r, i)&&x[i]<x[r])
                         ~~~~~~~~~~~~^~~~~~~~~~~
circuit.cpp:37:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=2; i<v.size(); ++i) {
               ~^~~~~~~~~

Subtask #1

85.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	512 KB	Output is correct
4	Correct	3 ms	512 KB	Output is correct
5	Correct	5 ms	640 KB	Output is correct
6	Correct	4 ms	640 KB	Output is correct
7	Correct	7 ms	1024 KB	Output is correct
8	Correct	4 ms	640 KB	Output is correct
9	Correct	4 ms	640 KB	Output is correct
10	Correct	4 ms	768 KB	Output is correct
11	Correct	5 ms	640 KB	Output is correct
12	Correct	6 ms	1024 KB	Output is correct
13	Correct	9 ms	1408 KB	Output is correct
14	Correct	10 ms	1536 KB	Output is correct
15	Correct	13 ms	2048 KB	Output is correct
16	Correct	22 ms	3704 KB	Output is correct
17	Correct	24 ms	3500 KB	Output is correct
18	Incorrect	38 ms	5880 KB	Output isn't correct
19	Runtime error	47 ms	11120 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
20	Runtime error	52 ms	11120 KB	Execution killed with signal 11 (could be triggered by violating memory limits)