Submission #585565

#	Time	Username	Problem	Language	Result	Execution time	Memory
585565		krit3379	Triangles (CEOI18_tri)	C++17	100 / 100	24 ms	2148 KiB

tri

#include<bits/stdc++.h>
using namespace std;
#include"trilib.h"
#define N 200005
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

deque<int> l,r,h;

bool ask(int i,int j,int k){return is_clockwise(i,j,k);}

deque<int> hull(deque<int> v){
    deque<int> h;
    for(auto x:v){
        while(h.size()>1&&!ask(h[h.size()-2],h[h.size()-1],x))h.pop_back();
        h.push_back(x);
    }
    return h;
}

int main(){
    int n,i;
    bool flag=true;
    n=get_n();
    for(i=3;i<=n;i++){
        if(ask(1,2,i))l.push_back(i);
        else r.push_back(i);
    }
    sort(l.begin(),l.end(),[&](const int a,int b){return ask(1,a,b);});
    sort(r.begin(),r.end(),[&](const int a,int b){return ask(1,a,b);});
    l.push_back(1);
    r.push_back(2);
    l=hull(l);
    r=hull(r);
    while(flag){
        flag=false;
        if(l.size()>1&&r.size()&&!ask(l[l.size()-2],l[l.size()-1],r[0])){
            l.pop_back();
            flag=true;
        }
        if(r.size()>1&&l.size()&&!ask(r[r.size()-2],r[r.size()-1],l[0])){
            r.pop_back();
            flag=true;
        }
        if(l.size()&&r.size()>1&&!ask(l[l.size()-1],r[0],r[1])){
            r.pop_front();
            flag=true;
        }
        if(r.size()&&l.size()>1&&!ask(r[r.size()-1],l[0],l[1])){
            l.pop_front();
            flag=true;
        }
    }
    give_answer(l.size()+r.size());
    return 0;
}

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