oj.uz

Submission #632483

# Submission time Handle Problem Language Result Execution time Memory
632483 2022-08-20T07:26:45 Z andrei_boaca Printed Circuit Board (CEOI12_circuit) C++14
10 / 100
 100 ms 10296 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].y!=v[b].y)
        return v[a].y<v[b].y;
    return v[a].x<v[b].x;
}
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
10.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Incorrect 3 ms 596 KB Output isn't correct
4 Incorrect 4 ms 660 KB Output isn't correct
5 Incorrect 13 ms 1268 KB Output isn't correct
6 Incorrect 13 ms 1316 KB Output isn't correct
7 Incorrect 27 ms 2388 KB Output isn't correct
8 Incorrect 10 ms 1108 KB Output isn't correct
9 Correct 8 ms 1108 KB Output is correct
10 Incorrect 14 ms 1364 KB Output isn't correct
11 Incorrect 15 ms 1456 KB Output isn't correct
12 Incorrect 21 ms 2416 KB Output isn't correct
13 Incorrect 40 ms 3400 KB Output isn't correct
14 Incorrect 53 ms 4400 KB Output isn't correct
15 Incorrect 58 ms 5328 KB Output isn't correct
16 Execution timed out 117 ms 10288 KB Time limit exceeded
17 Execution timed out 175 ms 10296 KB Time limit exceeded
18 Runtime error 61 ms 5068 KB Execution killed with signal 11
19 Runtime error 61 ms 5072 KB Execution killed with signal 11
20 Execution timed out 128 ms 8680 KB Time limit exceeded