oj.uz

답안 #932510

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
932510 2024-02-23T14:25:08 Z n0sk1ll Printed Circuit Board (CEOI12_circuit) C++17
10 / 100
 46 ms 9616 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

#define int li

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<<" ";
}

//Note to self: Check for overflow

/*

11
7 6
4 4
3 2
1 3
9 9
13 4
8 1
6 4
9 5
8 3
11 5

*/

Compilation message

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

Subtask #1
10.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Correct 2 ms 2648 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Incorrect 5 ms 3296 KB Output isn't correct
6 Incorrect 5 ms 3296 KB Output isn't correct
7 Incorrect 9 ms 3840 KB Output isn't correct
8 Incorrect 4 ms 3164 KB Output isn't correct
9 Incorrect 3 ms 3164 KB Output isn't correct
10 Incorrect 5 ms 3296 KB Output isn't correct
11 Incorrect 5 ms 3296 KB Output isn't correct
12 Incorrect 7 ms 3976 KB Output isn't correct
13 Incorrect 13 ms 4700 KB Output isn't correct
14 Incorrect 15 ms 5516 KB Output isn't correct
15 Incorrect 17 ms 5980 KB Output isn't correct
16 Incorrect 34 ms 9616 KB Output isn't correct
17 Incorrect 46 ms 9508 KB Output isn't correct
18 Runtime error 14 ms 6492 KB Execution killed with signal 11
19 Runtime error 14 ms 6600 KB Execution killed with signal 11
20 Runtime error 15 ms 6492 KB Execution killed with signal 11