Submission #650741

#	Time	Username	Problem	Language	Result	Execution time	Memory
650741		fatemetmhr	Triangles (CEOI18_tri)	C++17	75 / 100	3062 ms	1704 KiB

tri

//  ~Be name khoda~  //

#include<bits/stdc++.h>
#include "trilib.h"

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
#define cl       clear
#define endll    '\n'

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn  =  1e6   + 10;
const int maxn5 =  5e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const ll  inf   =  2e18;

int nxt[maxn5], pre[maxn5], av[maxn5];
int per[maxn5];

inline bool clk(int a, int b, int c){
    return is_clockwise(per[a], per[b], per[c]);
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    
    int n = get_n();
    nxt[1] = 2; nxt[2] = 3; nxt[3] = 1;
    pre[1] = 3; pre[2] = 1; pre[3] = 2;
    if(n == 3){
        give_answer(3);
        return 0;
    }
    int st = 1;
    for(int i = 1; i <= n; i++)
        per[i] = i;
    shuffle(per + 1, per + n + 1, rng);
    for(int i = 4; i <= n; i++){
        int out = -1;
        bool hullorder = clk(st, nxt[st], nxt[nxt[st]]);
        bool ans = clk(st, nxt[st], i);
        ans ^= hullorder;
        if(ans){
            out = st;
        }
        else{
            int have = nxt[st];
            int hi = 0;
            for(int i = 0; have != st; i++, have = nxt[have]){
                av[i] = have;
                hi = i;
            }
            int sz = hi;
            int lo = 0;
            while(hi - lo > 1){
                int mid = (lo + hi) >> 1;
                if(hullorder ^ clk(st, av[mid], i))
                    hi = mid;
                else
                    lo = mid;
            }
            //cout << "here " << st << ' ' << sz << ' ' << lo << ' ' << hi << endl;
            if(hi == sz && clk(st, pre[st], nxt[st]) != clk(st, pre[st], i)){
                lo = hi;
                //cout << "oh spc case " << endl;
                if(clk(av[lo], st, nxt[st]) != clk(av[lo], st, i))
                    out = av[lo];
            }
            else{
                if(clk(av[lo], av[lo + 1], nxt[av[lo + 1]]) != clk(av[lo], av[lo + 1], i))
                    out = av[lo];
            }
        }
        if(out == -1)
            continue;
        //cout << "it's " << out << endl;
        for(out = nxt[out]; ; out = nxt[out])
            if(clk(out, nxt[out], nxt[nxt[out]]) == clk(out, nxt[out], i))
                break;
        int r = out;
        //cout << "hola " << r << endl;
        for(out = pre[out]; ; out = pre[out])
            if(clk(out, pre[out], pre[pre[out]]) == clk(out, pre[out], i))
                break;
        int l = out;
        //cout << "wow it's " << l << endl;
        nxt[l] = i;
        pre[r] = i;
        nxt[i] = r;
        pre[i] = l;
        st = i;
        /*
        cout << "let's check " << i << endl;
        int j = st;
        cout << j << ' ';
        j = nxt[j];
        while(j != st){
            cout << j << ' ';
            j = nxt[j];
        }
        cout << endl;
        //*/
    }
    int num = 1;
    for(int i = nxt[st]; i != st; i = nxt[i]) num++;
    give_answer(num);
}

• Subtask 1: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 0 / 25