Submission #130571

#	Time	Username	Problem	Language	Result	Execution time	Memory
130571		Bench0310	Triangles (CEOI18_tri)	C++17	100 / 100	30 ms	2296 KiB

tri

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

using namespace std;

/*int get_n()
{
    return 10;
}

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

void give_answer(int s)
{
    cout << "answer: " << s << endl;
    exit(0);
}*/

int main()
{
    int n=get_n();
    vector<int> l,r;
    for(int i=3;i<=n;i++)
    {
        if(is_clockwise(1,2,i)) r.push_back(i);
        else l.push_back(i);
    }
    sort(l.begin(),l.end(),[](int a,int b){return is_clockwise(1,a,b);});
    sort(r.begin(),r.end(),[](int a,int b){return is_clockwise(1,a,b);});
    reverse(l.begin(),l.end());
    vector<int> one={1,2};
    for(int a:l)
    {
        while(one.size()>=2&&is_clockwise(one[one.size()-2],one.back(),a)) one.pop_back();
        one.push_back(a);
    }
    vector<int> two={1,2};
    for(int a:r)
    {
        while(two.size()>=2&&is_clockwise(two[two.size()-2],two.back(),a)==0) two.pop_back();
        two.push_back(a);
    }
    if(min(one.size(),two.size())==2) give_answer(max(one.size(),two.size()));
    else
    {
        one.erase(one.begin());
        two.erase(two.begin());
        one.push_back(1);
        while(1)
        {
            bool b=0;
            if(one.size()>=2&&is_clockwise(one[one.size()-2],one.back(),two.back()))
            {
                one.pop_back();
                b=1;
            }
            if(two.size()>=2&&is_clockwise(one.back(),two.back(),two[two.size()-2]))
            {
                two.pop_back();
                b=1;
            }
            if(!b) break;
        }
        reverse(one.begin(),one.end());
        reverse(two.begin(),two.end());
        two.pop_back();
        while(1)
        {
            bool b=0;
            if(one.size()>=2&&is_clockwise(one[one.size()-2],one.back(),two.back())==0)
            {
                one.pop_back();
                b=1;
            }
            if(two.size()>=2&&is_clockwise(one.back(),two.back(),two[two.size()-2])==0)
            {
                two.pop_back();
                b=1;
            }
            if(!b) break;
        }
        give_answer(one.size()+two.size());
    }
    return 0;
}

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