oj.uz

답안 #932506

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
932506 2024-02-23T14:23:09 Z n0sk1ll Printed Circuit Board (CEOI12_circuit) C++17
10 / 100
 46 ms 9208 KB 
#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;







//Note to self: Check for overflow

int x[100005],y[100005];
int ord[100005]; //order of the point

li dot(int a, int b, int c, int d)
{
    return (li)a*d-(li)b*c;
}

struct mojsort
{
    bool operator() (pair<pii,int> x, pair<pii,int> y)
    {
        return dot(x.xx.xx,x.xx.yy,y.xx.xx,y.xx.yy)>0;
    }
};

int N;
int fwt[100005];

void add(int i, int x)
{
    for (;i<=N;i+=(i&-i)) fwt[i]+=x;
}

int pre(int i)
{
    int ret=0;
    for (;i;i-=(i&-i)) ret+=fwt[i];
    return ret;
}

main()
{
    FAST;

    int n; cin>>n;
    ff(i,0,n) cin>>x[i]>>y[i];

    vector<pair<li,int>> tacke;
    ff(i,0,n) tacke.push_back({-((li)x[i]*x[i] + (li)y[i]*y[i]),i});
    sort(all(tacke));

    vector<pair<li,int>> duzi;
    ff(i,0,n)
    {
        int j=(i+1)%n;
        li d=max((li)x[i]*x[i]+(li)y[i]*y[i],(li)x[j]*x[j]+(li)y[j]*y[j]);
        duzi.push_back({-d,i});
    }
    sort(all(duzi));

    vector<pair<pii,int>> uglovi;
    ff(i,0,n) uglovi.push_back({{x[i],y[i]},i});
    sort(all(uglovi),mojsort());

    int idx=0;
    ff(i,0,n)
    {
        if (i==0 || dot(uglovi[i-1].xx.xx,uglovi[i-1].xx.yy,uglovi[i].xx.xx,uglovi[i].xx.yy)) ++idx;
        ord[uglovi[i].yy]=idx;
    }
    N=idx;

    vector<int> ans;

    while (!tacke.empty() && !duzi.empty())
    {
        if (tacke.back().xx >= duzi.back().xx)
        {
            if (pre(ord[tacke.back().yy])==0)
            {
                ans.pb(tacke.back().yy+1);
            }
            tacke.popb();
        }
        else
        {
            int i=duzi.back().yy;
            int j=(i+1)%n;
            int l=ord[i];
            int r=ord[j];
            if (l>r) swap(l,r);
            add(l,1);
            add(r+1,-1);
            duzi.popb();
        }
    }

    sort(all(ans));
    cout<<(int)ans.size()<<"\n";
    for (auto it : ans) cout<<it<<" ";
}

Compilation message

circuit.cpp:68:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   68 | main()
      | ^~~~

Subtask #1
10.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Incorrect 5 ms 1308 KB Output isn't correct
6 Incorrect 5 ms 1304 KB Output isn't correct
7 Incorrect 12 ms 2396 KB Output isn't correct
8 Incorrect 4 ms 1116 KB Output isn't correct
9 Incorrect 3 ms 1116 KB Output isn't correct
10 Incorrect 5 ms 1308 KB Output isn't correct
11 Incorrect 5 ms 1392 KB Output isn't correct
12 Incorrect 7 ms 2140 KB Output isn't correct
13 Incorrect 13 ms 2908 KB Output isn't correct
14 Incorrect 15 ms 3932 KB Output isn't correct
15 Incorrect 19 ms 4628 KB Output isn't correct
16 Incorrect 34 ms 9048 KB Output isn't correct
17 Incorrect 46 ms 9208 KB Output isn't correct
18 Runtime error 13 ms 3416 KB Execution killed with signal 11
19 Runtime error 13 ms 3416 KB Execution killed with signal 11
20 Runtime error 14 ms 3564 KB Execution killed with signal 11