oj.uz

Submission #632480

# Submission time Handle Problem Language Result Execution time Memory
632480 2022-08-20T07:23:33 Z andrei_boaca Printed Circuit Board (CEOI12_circuit) C++14
30 / 100
 100 ms 11676 KB 
#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
int n;
struct point
{
    int x,y,ang;
} v[100005],angle[100005];
bool comp(point a, point b)
{
    return a.y*b.x<a.x*b.y;
}
map<pii,int> nrm;
bool cmp(int a, int b)
{
    if(v[a].x!=v[b].x)
        return v[a].x<v[b].x;
    return v[a].y<v[b].y;
}
bool use[100005],spec[100005];
int aib[100005],times[100005];
int lsb(int x)
{
    return x&(-x);
}
void update(int poz,int val)
{
    for(int i=poz;i<=n;i+=lsb(i))
        aib[i]+=val;
}
int suma(int poz)
{
    int rez=0;
    for(int i=poz;i>=1;i-=lsb(i))
        rez+=aib[i];
    return rez;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;
        v[i]={x,y,0};
        int cmmdc=__gcd(x,y);
        x/=cmmdc;
        y/=cmmdc;
        angle[i]={x,y,0};
    }
    sort(angle+1,angle+n+1,comp);
   // cout<<'\n';
    for(int i=1;i<=n;i++)
    {
        pii a={angle[i].x,angle[i].y};
        nrm[a]=i;
    }
    for(int i=1;i<=n;i++)
    {
        int cmmdc=__gcd(v[i].x,v[i].y);
        int xa=v[i].x/cmmdc,ya=v[i].y/cmmdc;
        v[i].ang=nrm[{xa,ya}];
    }
    vector<int> ind;
    for(int i=1;i<=n;i++)
        ind.push_back(i);
    sort(ind.begin(),ind.end(),cmp);
    vector<int> sol;
    for(int i:ind)
    {
        int cnt=suma(v[i].ang)-times[i];
        if(cnt==0&&spec[v[i].ang]==0)
            sol.push_back(i);
        spec[v[i].ang]=1;
        int lft=i-1;
        if(i==1)
            lft=n;
        if(!use[lft])
        {
            int st=v[i].ang;
            int dr=v[lft].ang;
            if(st>dr)
                swap(st,dr);
            update(st,1);
            update(dr+1,-1);
            times[lft]++;
        }
        int rgt=i+1;
        if(i==n)
            rgt=1;
        if(!use[rgt])
        {
            int st=v[i].ang;
            int dr=v[rgt].ang;
            if(st>dr)
                swap(st,dr);
            update(st,1);
            update(dr+1,-1);
            times[rgt]++;
        }
        use[i]=1;
    }
    sort(sol.begin(),sol.end());
    cout<<sol.size()<<'\n';
    for(int i:sol)
        cout<<i<<' ';
    return 0;
}

Subtask #1
30.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Correct 1 ms 324 KB Output is correct
3 Incorrect 3 ms 596 KB Output isn't correct
4 Correct 4 ms 724 KB Output is correct
5 Incorrect 13 ms 1492 KB Output isn't correct
6 Incorrect 13 ms 1492 KB Output isn't correct
7 Incorrect 26 ms 2628 KB Output isn't correct
8 Incorrect 10 ms 1236 KB Output isn't correct
9 Correct 7 ms 1164 KB Output is correct
10 Incorrect 13 ms 1492 KB Output isn't correct
11 Incorrect 16 ms 1600 KB Output isn't correct
12 Correct 25 ms 2608 KB Output is correct
13 Incorrect 39 ms 3788 KB Output isn't correct
14 Correct 45 ms 4780 KB Output is correct
15 Correct 59 ms 5968 KB Output is correct
16 Execution timed out 126 ms 11580 KB Time limit exceeded
17 Execution timed out 166 ms 11676 KB Time limit exceeded
18 Runtime error 60 ms 6460 KB Execution killed with signal 11
19 Runtime error 60 ms 6476 KB Execution killed with signal 11
20 Execution timed out 126 ms 10188 KB Time limit exceeded