Submission #812948

#	Time	Username	Problem	Language	Result	Execution time	Memory
812948		DJeniUp	Triangles (CEOI18_tri)	C++17	55 / 100	630 ms	25164 KiB

tri

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

using namespace std;

typedef int ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pairll;
typedef pair<ll,ull>pairull;
typedef pair<ll,pairll>pair3l;
typedef long double ld;
typedef pair<ld,ld>pairld;

typedef pair<string,ll>pairsl;

#define fr first
#define sc second
#define pb push_back
#define endl '\n'
#define N 100007
#define MOD 1000000007
#define INF 10000000000007
#define eps 0.00000000001
#define A 50
#define PI 3.14159265359

ll n,d[40007],mn,mx;

deque<pairll>v,a;

vector<ll>h;

map<pair3l,ll>m;

ll cl(ll x,ll y,ll z){
    if(m[{x,{y,z}}]==0){
        m[{x,{y,z}}]=ll(is_clockwise(x,y,z))+1;
    }
    return m[{x,{y,z}}]-1;
}

pair3l S(ll l,ll r,ll z,ll l1,ll r1){
    //cout<<"? "<<l<<" "<<r<<" "<<l1<<" "<<r1<<endl;
    if(cl(v[l].fr,z,v[r].sc)==0){
        if(l1==1){
            if(cl(v[l].fr,z,v[l].sc)==0){
                l1=0;
                if(r1==1){
                    if(cl(v[r].fr,z,v[r].sc)==0)return {0,{0,0}};
                }else if(r1==0)return {0,{0,0}};
            }else r1=0;
        }else if(r1==1){
            if(cl(v[r].fr,z,v[r].sc)==0)return {0,{0,0}};
        }else return {0,{0,0}};
    }
    //cout<<l<<" "<<r<<endl;
    if(l==r){
        //cout<<"-"<<l<<endl;
        d[l]=z;
        mn=min(l,mn);
        mx=max(mx,l);
        return {1,{1,1}};
    }
    ll m1=(l+r)/2;
    pair3l tl=S(l,m1,z,l1,0);
    if(tl.fr==1){
        return {1,{tl.sc.fr,S(m1+1,r,z,tl.sc.sc,r1).sc.sc}};
    }else{
        tl=S(m1+1,r,z,0,r1);
        if(tl.sc.fr==1)return {1,{S(l,m1,z,0,tl.sc.fr).sc.fr,tl.sc.sc}};
        else return {1,{0,tl.sc.sc}};
    }

}

int main(){
    n=get_n();
    ll x=is_clockwise(1,3,2);
    if(x==1){
        v.pb({1,3});
        v.pb({3,2});
        v.pb({2,1});
    }else{
        v.pb({1,2});
        v.pb({2,3});
        v.pb({3,1});
    }
    for(int i=4;i<=n;i++){
        h.pb(i);
    }
    if(h.size()>0){
        for(int i=1;i<=10000000;i++){
            x=rand()%(n-3);
            ll y=rand()%(n-3);
            swap(h[x],h[y]);

        }
    }
    for(auto i:h){
        //m.clear();
        mn=v.size();
        mx=-1;
        pair3l tl=S(0,(v.size()-1)/2,i,0,0);
        if(tl.fr==1){
            S((v.size()-1)/2+1,v.size()-1,i,tl.sc.sc,tl.sc.fr);
        }else{
            tl=S((v.size()-1)/2+1,v.size()-1,i,0,0);
            if(tl.sc.sc==1)S(0,(v.size()-1)/2,i,tl.sc.sc,0);
            if(tl.sc.fr==1)S(0,(v.size()-1)/2,i,0,tl.sc.fr);

        }
        if(mn!=v.size()){
            if(mn==0){
                if(mx==v.size()-1){
                    while(d[v.size()-1]==i)v.pop_back();
                    v.pb({v.back().sc,i});
                    ll y=0;
                    while(d[y]==i){
                        y++;
                        v.pop_front();
                    }
                    v.push_front({i,v.front().fr});
                }else{
                    x=v.front().fr;
                    ll y=0;
                    while(d[y]==i){
                        y++;
                        v.pop_front();
                    }
                    v.push_front({i,v.front().fr});
                    v.push_front({x,i});
                }
            }else{
                    ll y=0;
                    while(d[y]!=i){
                        y++;
                        v.pb(v.front());
                        v.pop_front();
                    }
                    x=v.front().fr;
                    while(d[y]==i){
                        y++;
                        v.pop_front();
                    }
                    v.push_front({i,v.front().fr});
                    v.push_front({x,i});
            }
        }
        //cout<<"! "<<endl;
       // for(auto it:v)cout<<it.fr<<" "<<it.sc<<endl;
        //cout<<endl;
    }
    give_answer(v.size());
    return 0;
}

/*
8
1 1
1 18
4 16
6 14
7 11
6 8
4 4
15 10


*/

Compilation message (stderr)

tri.cpp: In function 'int main()':
tri.cpp:112:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::deque<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |         if(mn!=v.size()){
      |            ~~^~~~~~~~~~
tri.cpp:114:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::deque<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |                 if(mx==v.size()-1){
      |                    ~~^~~~~~~~~~~~

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