Submission #826305

#	Time	Username	Problem	Language	Result	Execution time	Memory
826305		gagik_2007	Triangles (CEOI18_tri)	C++17	100 / 100	34 ms	3976 KiB

tri

#include "trilib.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define ff first
#define ss second

ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=40007;
ll n,m,k;
mt19937 rnd(time(NULL));
int root;
bool comp(int x, int y){
    return is_clockwise(root,x,y);
}

void mergesort(vector<int>&a){
    if(a.size()<=1)return;
    int mid=rnd()%a.size();
    int midvl=a[mid];
    vector<int>lft,rgh;
    for(int i=0;i<a.size();i++){
        if(i!=mid){
            if(comp(a[i],a[mid]))lft.push_back(a[i]);
            else rgh.push_back(a[i]);
        }
    }
    mergesort(lft);
    mergesort(rgh);
    a.clear();
    for(int x:lft)a.push_back(x);
    a.push_back(midvl);
    for(int x:rgh)a.push_back(x);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    n=get_n();
    root=rnd()%n+1;
    vector<int>order;
    for(int i=1;i<=n;i++){
        if(i!=root){
            order.push_back(i);
        }
    }
    mergesort(order);
    order.push_back(root);
    set<int>s;
    int cur=0;
    vector<int>d(order.size());
    for(int x:order){
        s.insert(cur);
        d[cur]=x;
        // cout<<x<<" ";
        cur++;
    }
    // cout<<endl;
    bool gna=true;
    auto it=s.begin();
    auto lst=(--s.end());
    auto nxt=(++s.begin());
    int cnt=0;
    while(cnt<100000){
        // cout<<s.size()<<" "<<d[*lst]<<" "<<d[*it]<<" "<<d[*nxt]<<endl;
        if(gna){
            if(!is_clockwise(d[*lst],d[*it],d[*nxt])){
                gna=false;
                s.erase(it);

                // get new iterators
                it=lst;
                it++;
                if(it==s.end())it=s.begin();
                nxt=it;
                nxt++;
                if(nxt==s.end())nxt=s.begin();

                // go back 1 step
                nxt=it;
                it=lst;
                if(lst==s.begin())lst=s.end();
                lst--;
            }
            else{
                // go forward 1 step
                lst=it;
                it=nxt;
                nxt++;
                if(nxt==s.end())nxt=s.begin();
            }
        }
        else{
            if(is_clockwise(d[*lst],d[*it],d[*nxt])){
                // stop going back and go forward 1 step
                gna=true;
                lst=it;
                it=nxt;
                nxt++;
                if(nxt==s.end())nxt=s.begin();
            }
            else{
                // erase the bad element
                s.erase(it);

                // get new iterators
                it=lst;
                it++;
                if(it==s.end())it=s.begin();
                nxt=it;
                nxt++;
                if(nxt==s.end())nxt=s.begin();

                // go back 1 step
                nxt=it;
                it=lst;
                if(lst==s.begin())lst=s.end();
                lst--;
            }
        }
        cnt++;
    }
    give_answer(s.size());
    return 0;
}

Compilation message (stderr)

tri.cpp: In function 'void mergesort(std::vector<int>&)':
tri.cpp:29:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int i=0;i<a.size();i++){
      |                 ~^~~~~~~~~

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