Submission #142947

#	Time	Username	Problem	Language	Result	Execution time	Memory
142947		shayan_p	Triangles (CEOI18_tri)	C++14	75 / 100	138 ms	3796 KiB

tri

// only miss the sun when it starts to snow

#include<bits/stdc++.h>

#include "trilib.h"

#define F first
#define S second
#define PB push_back
#define PF push_front
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

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

const int maxn=1e5+10,mod=1e9+7;
const ll inf=1e18;
/*
int get_n(){ //
    return 4;
}
int give_answer(int x){
    cout<<"ANS "<<x<<endl;
    exit(0);
}
bool is_clockwise(int a,int b,int c){
    cout<<a<<" "<<b<<" "<<c<<endl;
    bool x; cin>>x;
    return x;
    }*/

deque<int> solve(deque<int>v){
    /*    cout<<"GONNA SOLVE ";
    for(int x:v)
	cout<<x<<" ";
    cout<<endl;
    */
    if(sz(v)<=2) return v;
    random_shuffle(v.begin(), v.end());
    
    deque<int> v1, v2;

    int A= v.back(), B=v[sz(v)-2];
    v.pop_back(), v.pop_back();

    for(int i=0; i<sz(v); i++){
	if(is_clockwise(A,B,v[i]) == 0) v1.PB(v[i]);
	else v2.PB(v[i]);
    }
    if(v1.empty()){
	v2.PB(B);
	v2=solve(v2);

	while(v2.front() != B)
	    v2.PF(v2.back()), v2.pop_back();
	while(sz(v2)>2 && is_clockwise(v2[ sz(v2)-2 ], v2[sz(v2)-1], A) == 0) v2.pop_back();
	v2.PB(A);
	v1=v2;
    }
    else if(v2.empty()){
	v1.PB(A);
	v1=solve(v1);

	while(v1.front() != A)
	    v1.PF(v1.back()), v1.pop_back();
	while(sz(v1)>2 && is_clockwise(v1[ sz(v1)-2 ], v1[ sz(v1)-1 ], B) == 0) v1.pop_back();
	v1.PB(B);
    }
    else{
	v1.PB(A), v1.PB(B);
	v2.PB(A), v2.PB(B);
	v1= solve(v1), v2=solve(v2);

	//	cout<<"ALSKASLA "<<endl;

	reverse(v2.begin(), v2.end());
	while(v1.front()!=A || v1.back()!=B)
	    v1.PF(v1.back()), v1.pop_back();
	while(v2.front()!=A || v2.back()!=B)
	    v2.PF(v2.back()), v2.pop_back();
	v2.pop_back();
	v1.pop_front();
	/*
	cout<<"SALAAAA ";
	for(int x:v1) cout<<x<<" ";
	cout<<endl;
	cout<<"SALLAA2 ";
	for(int x:v2) cout<<x<<" ";
	cout<<endl;
	*/	
	while(true){
	    if(sz(v1)>1 && is_clockwise(v1[sz(v1)-2], v1[sz(v1)-1], v2.back()) == 0)
		v1.pop_back();
	    else if(sz(v2)>1 && is_clockwise(v1[sz(v1)-1], v2[sz(v2)-1], v2[sz(v2)-2]) == 0)
		v2.pop_back();
	    else
		break;
	}
	while(true){
	    if(sz(v2)>1 && is_clockwise(v2[1], v2[0], v1[0]) == 0)
		v2.pop_front();
	    else if(sz(v1)>1 && is_clockwise(v2[0], v1[0], v1[1]) == 0)
		v1.pop_front();
	    else
		break;
	}
	reverse(v2.begin(), v2.end());
	for(int x:v2)
	    v1.PB(x);
    }
    /*   cout<<"END "<<"   ";
    for(int x:v1)
	cout<<x<<" ";
	cout<<endl;*/
    return v1;
}

int main(){
    int n=get_n();
    srand(time(0));
    deque<int> v;
    for(int i=1;i<=n;i++)
	v.PB(i);
    v= solve(v);
    give_answer(sz(v));
}

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