Submission #650742

#	Time	Username	Problem	Language	Result	Execution time	Memory
650742		fatemetmhr	Triangles (CEOI18_tri)	C++17	100 / 100	471 ms	2388 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 int sq    =  200;
const ll  inf   =  2e18;

int nxt[maxn5], pre[maxn5];
int per[maxn5], st, sqnxt[maxn5];

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

inline int get(int d){
    int v = st;
    while(d >= sq){
        d -= sq;
        v = sqnxt[v];
    }
    while(d--)
        v = nxt[v];
    return v;
}

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;
    int need = sq;
    sqnxt[1] = 1; sqnxt[2] = 2; sqnxt[3] = 3;
    while(need--){
        sqnxt[1] = nxt[sqnxt[1]];
        sqnxt[2] = nxt[sqnxt[2]];
        sqnxt[3] = nxt[sqnxt[3]];
    }
    if(n == 3){
        give_answer(3);
        return 0;
    }
    st = 1;
    int sz = 3;
    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 lo = 0, hi = sz - 2;
            while(hi - lo > 1){
                int mid = (lo + hi) >> 1;
                if(hullorder ^ clk(st, get(mid + 1), i))
                    hi = mid;
                else
                    lo = mid;
            }
            //cout << "here " << st << ' ' << sz << ' ' << lo << ' ' << hi << endl;
            if(hi == sz - 2 && clk(st, pre[st], nxt[st]) != clk(st, pre[st], i)){
                lo = hi;
                //cout << "oh spc case " << endl;
                if(clk(pre[st], st, nxt[st]) != clk(pre[st], st, i))
                    out = pre[st];
            }
            else{
                int lolo = get(lo + 1);
                if(clk(lolo, nxt[lolo], nxt[nxt[lolo]]) != clk(lolo, nxt[lolo], i))
                    out = lolo;
            }
        }
        //cout << "chaka chaka " << i << ' ' << out << endl;
        if(out == -1)
            continue;
        for(out = nxt[out]; ; out = nxt[out])
            if(clk(out, nxt[out], nxt[nxt[out]]) == clk(out, nxt[out], i))
                break;
        int r = out;
        for(out = pre[out]; ; out = pre[out]){
            if(clk(out, pre[out], pre[pre[out]]) == clk(out, pre[out], i))
                break;
            sz--;
        }
        sz++;
        int l = out;
        //cout << "hola " << r << endl;
        //cout << "wow it's " << l << endl;
        nxt[l] = i;
        pre[r] = i;
        nxt[i] = r;
        pre[i] = l;
        st = i;
        int need = sq;
        int have = i;
        while(need--)
            have = nxt[have];
        sqnxt[i] = have;
        need = sq + 4;
        have = i;
        while(need--){
            have = pre[have];
            sqnxt[have] = pre[sqnxt[nxt[have]]];
        }
        /*
        cout << "let's check " << i << endl;
        int j = st;
        cout << j << ' ';
        j = nxt[j];
        while(j != st){
            cout << j << ' ';
            j = nxt[j];
        }
        cout << endl;
        cout << "and finaly " << sz << 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: 25 / 25