Submission #116211

#	Time	Username	Problem	Language	Result	Execution time	Memory
116211		JohnTitor	Triangles (CEOI18_tri)	C++11	100 / 100	56 ms	3492 KiB

tri

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
#define __builtin_popcount __builtin_popcountll
using ll=long long; using ld=long double;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const ld pi=acos(0)*2;
template <typename T> inline void read(T &x){char c; bool nega=0; while((!isdigit(c=getchar()))&&(c!='-')); if(c=='-'){nega=1; c=getchar();} x=c-48; while(isdigit(c=getchar())) x=x*10+c-48; if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10); putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){ putchar('-'); x=-x;} writep(x);}
template <typename T> inline void writeln(T x){write(x); putchar('\n');}
#define taskname "Triangles"
#ifndef Aria
#include "trilib.h"
#else
    int get_n(){
        int n;
        printf("get_n: \n");
        read(n);
        return n;
    }
    bool is_clockwise(int a, int b, int c){
        printf("is_clockwise %d %d %d: \n", a, b, c);
        bool res;
        read(res);
        return res;
    }
    void give_answer(int s){
        printf("ans = %d\n", s);
    }
#endif // Aria
int n;
int a[40001];
#define cw is_clockwise
void quicksort(int l, int r){
    if(l>=r) return;
    int m=rng()%(r-l+1)+l;
    vector <int> left, right;
    FOR(i, l, r) if(i!=m) if(cw(1, a[m], a[i])) left.pb(a[i]);
    else right.pb(a[i]);
    left.pb(a[m]);
    m=l+left.size()-1;
    for(int x: right) left.pb(x);
    FOR(i, l, r) a[i]=left[i-l];
    left.clear();
    right.clear();
    quicksort(l, m-1);
    quicksort(m+1, r);
}
deque <int> v;
int main(){
    #ifdef Aria
        if(fopen(taskname".in", "r"))
            freopen(taskname".in", "r", stdin);
    #endif // Aria
    n=get_n();
    FOR(i, 1, n) a[i]=i;
    quicksort(2, n);
//    FOR(i, 1, n) bug(a[i]);
    FOR(i, 1, n){
        while(v.size()>=2){
            if(cw(v[v.size()-2], v[v.size()-1], a[i])) v.pop_back();
            else break;
        }
        v.pb(a[i]);
    }
//    bug(v.size());
//    for(int x: v) bug(x);
    while(true){
        int sz=v.size();
        while(cw(v.back(), v[0], v[1])) v.pop_front();
        while(cw(v[v.size()-2], v.back(), v[0])) v.pop_back();
        if(v.size()==sz) break;
    }
    give_answer(v.size());
}

Compilation message (stderr)

tri.cpp: In function 'void quicksort(int, int)':
tri.cpp:46:20: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
     FOR(i, l, r) if(i!=m) if(cw(1, a[m], a[i])) left.pb(a[i]);
                    ^
tri.cpp: In function 'int main()':
tri.cpp:80:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(v.size()==sz) break;
            ~~~~~~~~^~~~

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