Submission #259802

#	Time	Username	Problem	Language	Result	Execution time	Memory
259802		MKopchev	Triangles (CEOI18_tri)	C++14	100 / 100	41 ms	2176 KiB

tri

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

int n;
/*
int get_n()
{
    cin>>n;
    return n;
}
bool is_clockwise(int i,int j,int k)
{
    cout<<i<<" "<<j<<" "<<k<<" -> ";
    int ret;
    cin>>ret;
    return ret;
}
void give_answer(int sz)
{
    cout<<sz<<endl;
}
*/
set<int> hull;

vector<int> points[2];

bool cmp(int a,int b)
{
    return is_clockwise(a,1,b);
}

stack<int> hulls[2];

bool pop_wrong()
{
    int was=points[0].size()+points[1].size();
    /*
    for(auto k:points[0])cout<<k<<" ";cout<<endl;
    for(auto k:points[1])cout<<k<<" ";cout<<endl;
    */
    while(points[0].size()>=2&&is_clockwise(points[1][0],points[0][points[0].size()-1],points[0][points[0].size()-2])==1)points[0].pop_back();
    /*
    for(auto k:points[0])cout<<k<<" ";cout<<endl;
    for(auto k:points[1])cout<<k<<" ";cout<<endl;
    */
    while(points[1].size()>=2&&is_clockwise(points[0][0],points[1][points[1].size()-1],points[1][points[1].size()-2])==1)points[1].pop_back();

    reverse(points[0].begin(),points[0].end());
    reverse(points[1].begin(),points[1].end());

    while(points[0].size()>=2&&is_clockwise(points[1][0],points[0][points[0].size()-1],points[0][points[0].size()-2])==0)points[0].pop_back();

    while(points[1].size()>=2&&is_clockwise(points[0][0],points[1][points[1].size()-1],points[1][points[1].size()-2])==0)points[1].pop_back();

    reverse(points[0].begin(),points[0].end());
    reverse(points[1].begin(),points[1].end());

    int is=points[0].size()+points[1].size();

    return was>is;
}

int main()
{
	n=get_n();

	for(int i=3;i<=n;i++)
        points[is_clockwise(1,2,i)].push_back(i);

    //cout<<"---"<<endl;

    sort(points[0].begin(),points[0].end(),cmp);

    //cout<<"---"<<endl;

    sort(points[1].begin(),points[1].end(),cmp);
    /*
    cout<<"0: ";for(auto k:points[0])cout<<k<<" ";cout<<endl;
    cout<<"1: ";for(auto k:points[1])cout<<k<<" ";cout<<endl;
    */
    hulls[0].push(2);
    for(auto k:points[0])
        {
            while(hulls[0].size()>=2)
            {
                int tp=hulls[0].top();
                hulls[0].pop();

                int prv=hulls[0].top();

                if(is_clockwise(prv,tp,k)==0)
                {
                    hulls[0].push(tp);
                    break;
                }
            }

            hulls[0].push(k);
        }

    hulls[1].push(1);

    for(auto k:points[1])
        {
            while(hulls[1].size()>=2)
            {
                int tp=hulls[1].top();
                hulls[1].pop();

                int prv=hulls[1].top();

                if(is_clockwise(prv,tp,k)==0)
                {
                    hulls[1].push(tp);
                    break;
                }
            }

            hulls[1].push(k);
        }

    for(int w=0;w<2;w++)
    {
        points[w]={};

        while(hulls[w].size())
        {
            points[w].push_back(hulls[w].top());
            hulls[w].pop();
        }
    }

    while(pop_wrong());

    give_answer(points[0].size()+points[1].size());
    /*
    for(auto k:points[0])cout<<k<<" ";cout<<endl;
    for(auto k:points[1])cout<<k<<" ";cout<<endl;
    */
	return 0;
}

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