Submission #873385

#	Time	Username	Problem	Language	Result	Execution time	Memory
873385		Darren0724	Triangles (CEOI18_tri)	C++17	100 / 100	19 ms	3024 KiB

tri

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

using namespace std;


int32_t main() {
    int n=get_n();
    //int cnt=0;
    //int ans=0;
    //int i=1;
    vector<int> r[2];
    //vector<int> ans[2];
    vector<int> s[2];
    for(int j=3;j<=n;j++){
        int t=is_clockwise(1,2,j);
        r[t].push_back(j);
    }
    for(int y=0;y<2;y++){
        sort(r[y].begin(),r[y].end(),[&](int a,int b){return is_clockwise(1,b,a);});
        r[y].push_back(y==0?1:2);
    }
    for(int j:r[1]){
        r[0].push_back(j);
    }
    vector<int> t;
    for(int i:r[0]){
        //cout<<i<<endl;
        while(t.size()>1&&is_clockwise(t.end()[-2],t.end()[-1],i)){
            t.pop_back();
        }
        t.push_back(i);
    }
    int tmp=t.size();
    //cout<<tmp<<endl;
    for(int i:r[0]){
        while(t.size()>1&&is_clockwise(t.end()[-2],t.end()[-1],i)){
            t.pop_back();
        }
        t.push_back(i);
    }
    give_answer(t.size()-tmp);

    return 0;
}

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