Submission #119206

#	Time	Username	Problem	Language	Result	Execution time	Memory
119206		davitmarg	Triangles (CEOI18_tri)	C++17	0 / 100	19 ms	384 KiB

tri

/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <stack>
#include <cassert>
#include <iterator>
#include <bitset>
#include <fstream>

#ifndef death
    #include<trilib.h>
#endif // death

#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;

#ifdef death

int get_n()
{
    cout<<"N::"<<endl;
    int x;
    cin>>x;
    return x;
}

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

void give_answer(int x)
{
    cout<<x<<endl;
}

#endif // death

map<pair<int,pair<int,int>>,bool> used;
map<pair<int,pair<int,int>>,bool> pre;

bool cw(int a,int b,int c)
{
    if(used[MP(a,MP(b,c))])
        return pre[MP(a,MP(b,c))];
    used[MP(a,MP(b,c))]=1;
     return pre[MP(a,MP(b,c))]=is_clockwise(a,b,c);
}

bool ccw(int a,int b,int c)
{
    return !cw(a,b,c);
}

int convex(vector<int>& p)
{
    vector<int> up,down;
    up.PB(p[0]);
    down.PB(p[0]);
    for(int i=1;i<p.size();i++)
    {
        if(i==p.size()-1 || cw(p[0],p[i],p[p.size()-1]))
        {
            while(up.size()>1 && !cw(up[up.size()-2],up[up.size()-1],p[i]) )
                up.pop_back();
            up.PB(p[i]);
        }

        if(i==p.size()-1 || ccw(p[0],p[i],p[p.size()-1]))
        {
            while(down.size()>1 && !cw(down[down.size()-2],down[down.size()-1],p[i]) )
                down.pop_back();
            down.PB(p[i]);
        }
    }
    return up.size()+down.size()-2;
}

int ans,n;
vector<int> p;
int main()
{
    n=get_n();
    for(int i=1;i<=n;i++)
        p.PB(i);
    for(int i=1;i<=20000;i++)
    {
        random_shuffle(all(p));
        ans=max(ans,convex(p));
    }
    give_answer(ans);
	return 0;
}


/*


*/

Compilation message (stderr)

tri.cpp: In function 'int convex(std::vector<int>&)':
tri.cpp:76:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<p.size();i++)
                 ~^~~~~~~~~
tri.cpp:78:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(i==p.size()-1 || cw(p[0],p[i],p[p.size()-1]))
            ~^~~~~~~~~~~~
tri.cpp:85:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(i==p.size()-1 || ccw(p[0],p[i],p[p.size()-1]))
            ~^~~~~~~~~~~~

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