Submission #812855

#	Time	Username	Problem	Language	Result	Execution time	Memory
812855		DJeniUp	Triangles (CEOI18_tri)	C++17	0 / 100	1 ms	212 KiB

tri

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

using namespace std;

typedef long long 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;

pair3l S(ll l,ll r,ll z,ll l1,ll r1){
    if(l1==1){
        if(is_clockwise(v[l].fr,z,v[l].sc)==0 && r1==0)return {0,{0,0}};
    }
    if(r1==1){
        if(is_clockwise(v[r].fr,z,v[r].sc)==0)return {0,{0,0}};
    }
    if(is_clockwise(v[l].fr,z,v[r].sc)==0 && l1==0 && r1==0)return {0,{0,0}};

    if(l==r){
        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);
        return {1,{S(l,m1,z,l1,tl.sc.fr).sc.fr,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++){
        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);
            S(0,(v.size()-1)/2,i,tl.sc.sc,tl.sc.fr);
        }
        if(mn!=v.size()){
            if(mn==0){
                if(mx==v.size()){
                    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;
}

Compilation message (stderr)

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

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