Submission #78186

#	Time	Username	Problem	Language	Result	Execution time	Memory
78186		igzi	Triangles (CEOI18_tri)	C++17	100 / 100	1092 ms	25072 KiB

tri

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

using namespace std;

vector <int> v;
int n,i;
/*
int get_n(){
cin>>n;
return n;
}

bool is_clockwise(int a, int b, int c){
cout<<a<<" "<<b<<" "<<c<<endl;
int ans;
cin>>ans;
return ans;
}

void give_answer(int s) {cout<<s<<endl;}*/

void resi(int l,int d,int val){
int x,n=v.size();
while(true){
if(is_clockwise(v[(l-1+n)%n],v[(l+n)%n],val)) {x=(l+n)%n; break;}
v[(l+n)%n]=0;
l--;
}
while(true){
if(is_clockwise(val,v[d%n],v[(d+1)%n])) break;
v[d%n]=0;
d++;
}
v.insert(v.begin()+(x+1),val);
for(int i=0;i<v.size();i++){
    if(v[i]==0) {v.erase(v.begin()+i); i--;}
}
}

int main()
{
    n=get_n();
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    if(!is_clockwise(1,2,3)) swap(v[0],v[2]);
    for(i=4;i<=n;i++){
        if(!is_clockwise(v[0],v[1],i)) {resi(0,1,i); continue;}
        if(!is_clockwise(v.back(),v[0],i)) {resi(v.size()-1,0,i); continue;}
        int l,d,m;
        l=1;
        d=v.size()-1;
        while(d-l>1){
            m=(l+d)/2;
            if(is_clockwise(v[0],v[m],i)) l=m;
            else d=m;
        }
        if(is_clockwise(v[l],v[d],i)) continue;
        resi(l,d,i);
    }
    give_answer(v.size());
    return 0;
}

Compilation message (stderr)

tri.cpp: In function 'void resi(int, int, int)':
tri.cpp:36:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(int i=0;i<v.size();i++){
             ~^~~~~~~~~

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