#include <bits/stdc++.h>
using namespace std;
#define getchar_unlocked getchar
#define putchar_unlocked putchar
int in() {
char c=0;
while(c<'0'||c>'9')
c=getchar_unlocked();
int r=0;
while(c>='0'&&c<='9') {
r=r*10+c-'0';
c=getchar_unlocked();
}
return r;
}
void out(int x) {
int c=0, r=0;
for(; x%10==0; ++c, x/=10);
for(; x; x/=10)
r=r*10+x%10;
for(; r; r/=10)
putchar_unlocked(r%10+'0');
while(c--)
putchar_unlocked('0');
}
const int mxN=2e5, mxA=1e6;
int n, b[2][mxN], c[mxA+1], d[mxN+1], e1[mxN], e2[mxN], a1, t[2][mxN], tp[mxN];
long long x[mxN+1], y[mxN+1];
array<int, 3> a[mxN];
vector<array<int, 2>> r[18];
bool ans[mxN];
bool cw(int a, int b, int c) {
return (y[c]-y[a])*(x[b]-x[a])<(y[b]-y[a])*(x[c]-x[a]);
}
bool scmp(const int &i, const int &j) {
if(i<0)
return 0;
if(j<0)
return 1;
if(e1[i]==e1[j])
return d[e2[i]]<d[e2[j]]?!cw(e1[j], e2[j], e2[i]):cw(e1[i], e2[i], e2[j]);
return d[e1[i]]<d[e1[j]]?cw(e1[i], e2[i], e1[j]):!cw(e1[j], e2[j], e1[i]);
}
int main() {
n=in();
for(int i=0; i<n; ++i) {
x[i]=in(), y[i]=in();
long long z1=y[i]*mxA*mxA/x[i]-mxA, z2=z1/mxA, z3=z2/mxA;
a[i]={z1-z2*mxA, z2-z3*mxA, z3};
}
x[n]=x[0];
y[n]=y[0];
iota(b[0], b[0]+n, 0);
for(int k=0; k<3; ++k) {
memset(c+1, 0, 4*mxA);
for(int i=0; i<n; ++i)
++c[a[i][k]+1];
for(int i=0; i<mxA; ++i)
c[i+1]+=c[i];
for(int i=n-1; ~i; --i)
b[k&1^1][--c[a[b[k&1][i]][k]+1]]=b[k&1][i];
}
memset(tp, -1, 4*n);
for(int i=0, j=0; i<n; i=j) {
for(; j<n&&a[b[1][j]]==a[b[1][i]]; ++j) {
d[b[1][j]]=i;
if(tp[i]<0||x[b[1][j]]+y[b[1][j]]<x[tp[i]]+y[tp[i]])
tp[i]=b[1][j];
}
}
d[n]=d[0];
for(int i=0; i<n; ++i) {
e1[i]=i;
e2[i]=i+1;
if(d[e2[i]]<d[e1[i]])
swap(e1[i], e2[i]);
if(d[e1[i]]<d[e2[i]]) {
int k=31-__builtin_clz(d[e2[i]]-d[e1[i]]);
r[k].push_back({d[e1[i]], i});
r[k].push_back({d[e2[i]]-(1<<k), i});
}
}
memset(t[1], -1, 4*n);
for(int i=17; ~i; --i) {
for(array<int, 2> a : r[i])
t[i&1][a[0]]=min(a[1], t[i&1][a[0]], scmp);
if(i) {
memset(t[i&1^1], -1, 4*n);
for(int j=0; j<=n-(1<<i); ++j) {
t[i&1^1][j]=min(t[i&1][j], t[i&1^1][j], scmp);
t[i&1^1][j+(1<<i-1)]=min(t[i&1][j], t[i&1^1][j+(1<<i-1)], scmp);
}
}
}
for(int i=0; i<n; ++i)
if(~tp[i]&&(t[0][i]<0||!cw(e1[t[0][i]], e2[t[0][i]], tp[i])))
ans[tp[i]]=1;
for(int i=0; i<n; ++i)
a1+=ans[i];
out(a1);
putchar_unlocked('\n');
for(int i=0; i<n; ++i) {
if(ans[i]) {
out(i+1);
putchar_unlocked(' ');
}
}
}
Compilation message
circuit.cpp: In function 'int main()':
circuit.cpp:56:11: warning: narrowing conversion of '(z1 - (z2 * 1000000))' from 'long long int' to 'int' inside { } [-Wnarrowing]
a[i]={z1-z2*mxA, z2-z3*mxA, z3};
~~^~~~~~~
circuit.cpp:56:22: warning: narrowing conversion of '(z2 - (z3 * 1000000))' from 'long long int' to 'int' inside { } [-Wnarrowing]
a[i]={z1-z2*mxA, z2-z3*mxA, z3};
~~^~~~~~~
circuit.cpp:56:33: warning: narrowing conversion of 'z3' from 'long long int' to 'int' inside { } [-Wnarrowing]
a[i]={z1-z2*mxA, z2-z3*mxA, z3};
^
circuit.cpp:68:7: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
b[k&1^1][--c[a[b[k&1][i]][k]+1]]=b[k&1][i];
~^~
circuit.cpp:95:14: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
memset(t[i&1^1], -1, 4*n);
~^~
circuit.cpp:97:8: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
t[i&1^1][j]=min(t[i&1][j], t[i&1^1][j], scmp);
~^~
circuit.cpp:97:35: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
t[i&1^1][j]=min(t[i&1][j], t[i&1^1][j], scmp);
~^~
circuit.cpp:98:8: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
t[i&1^1][j+(1<<i-1)]=min(t[i&1][j], t[i&1^1][j+(1<<i-1)], scmp);
~^~
circuit.cpp:98:21: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
t[i&1^1][j+(1<<i-1)]=min(t[i&1][j], t[i&1^1][j+(1<<i-1)], scmp);
~^~
circuit.cpp:98:44: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
t[i&1^1][j+(1<<i-1)]=min(t[i&1][j], t[i&1^1][j+(1<<i-1)], scmp);
~^~
circuit.cpp:98:57: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
t[i&1^1][j+(1<<i-1)]=min(t[i&1][j], t[i&1^1][j+(1<<i-1)], scmp);
~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
4352 KB |
Output is correct |
| 2 |
Correct |
8 ms |
4352 KB |
Output is correct |
| 3 |
Correct |
10 ms |
4736 KB |
Output is correct |
| 4 |
Correct |
9 ms |
4736 KB |
Output is correct |
| 5 |
Correct |
11 ms |
5248 KB |
Output is correct |
| 6 |
Correct |
11 ms |
5120 KB |
Output is correct |
| 7 |
Correct |
16 ms |
6016 KB |
Output is correct |
| 8 |
Correct |
11 ms |
4864 KB |
Output is correct |
| 9 |
Correct |
9 ms |
5120 KB |
Output is correct |
| 10 |
Correct |
12 ms |
5120 KB |
Output is correct |
| 11 |
Correct |
13 ms |
5248 KB |
Output is correct |
| 12 |
Correct |
15 ms |
6016 KB |
Output is correct |
| 13 |
Correct |
22 ms |
6772 KB |
Output is correct |
| 14 |
Correct |
24 ms |
7680 KB |
Output is correct |
| 15 |
Correct |
26 ms |
8172 KB |
Output is correct |
| 16 |
Correct |
55 ms |
12008 KB |
Output is correct |
| 17 |
Correct |
66 ms |
12264 KB |
Output is correct |
| 18 |
Correct |
90 ms |
19736 KB |
Output is correct |
| 19 |
Execution timed out |
101 ms |
19936 KB |
Time limit exceeded |
| 20 |
Execution timed out |
140 ms |
19756 KB |
Time limit exceeded |
