Submission #503649

#	Time	Username	Problem	Language	Result	Execution time	Memory
503649		andrei_boaca	Triangles (CEOI18_tri)	C++14	0 / 100	1 ms	204 KiB

tri

#include <bits/stdc++.h>
#include "trilib.h"
//#include "trilib.c"
using namespace std;
mt19937 rng(time(NULL));
map<vector<int>,bool> f;
set<int> border;
vector<int> stiva,q;
int root;
int calls;
bool isgood(int a,int b,int c)
{
    vector<int> v;
    v.push_back(a);
    v.push_back(b);
    v.push_back(c);
    sort(v.begin(),v.end());
    if(f.count(v)==0)
    {
        f[v]=is_clockwise(v[0],v[1],v[2]);
        calls++;
        assert(calls<=1e6);
    }
    bool ans=f[v];
    int nr=0;
    if(a!=v[0])
        nr++;
    if(b!=v[1])
        nr++;
    if(c!=v[2])
        nr++;
    if(nr%2==0&&nr>0)
        ans=!ans;
    return ans;
}
bool comp(int a, int b)
{
    if(is_clockwise(root,a,b))
        return 1;
    return 0;
}
int main()
{
    int n;
    n=get_n();
    int start=1;
    int j=0;
    if(start==2)
        j=1;
    else
        j=2;
    for(int i=1;i<=n;i++)
        if(start!=i&&j!=i)
            if(!is_clockwise(start,j,i))
                j=i;
    stiva.push_back(j);
    root=j;
    for(int i=1;i<=n;i++)
        if(i!=root)
            q.push_back(i);
    sort(q.begin(),q.end(),comp);
    stiva.push_back(q[0]);
    for(int i=1;i<q.size();i++)
    {
        int nod=q[i];
        while(stiva.size()>2)
        {
            int lg=stiva.size();
            int b=stiva[lg-1];
            int a=stiva[lg-2];
            if(!is_clockwise(a,b,nod))
                stiva.pop_back();
            else
                break;
        }
        stiva.push_back(nod);
    }
    give_answer(stiva.size());
    for(auto i:stiva)
        cout<<i<<' ';
    return 0;
}

Compilation message (stderr)

tri.cpp: In function 'int main()':
tri.cpp:63:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for(int i=1;i<q.size();i++)
      |                 ~^~~~~~~~~

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