Submission #950578

#	Time	Username	Problem	Language	Result	Execution time	Memory
950578		berr	Triangles (CEOI18_tri)	C++17	55 / 100	8 ms	748 KiB

tri

#include <bits/stdc++.h>
using namespace std;
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "trilib.h"
 
map<array<short, 3>, int> mp;
 
/*
static int n;
static long long *x, *y;
static int queries=0;
 
static void init() {
    static int is_inited=0;
    if (is_inited)
        return;
    is_inited=1;
    assert(scanf("%d", &n)==1);
    x=(long long*)malloc((n+1)*sizeof(long long));
    y=(long long*)malloc((n+1)*sizeof(long long));
    for (int i=1; i<=n; i++)
        assert(scanf("%lld%lld", &x[i], &y[i])==2);
}
 
int get_n() {
    init();
    return n;
}
 
int is_clockwise(int a, int b, int c) {
    init();
    assert(a>=1 && a<=n);
    assert(b>=1 && b<=n);
    assert(c>=1 && c<=n);
    assert(a!=b && a!=c && b!=c);
    queries++;
        if(queries == 1000 * 1000 + 1)
            printf("Too many queries!");
    return (x[b]-x[a])*(y[c]-y[a])-(x[c]-x[a])*(y[b]-y[a])<0;
}
 
void give_answer(int s) {
    init();
    printf("%d\n", s);
}*/
 
 int is_clock(int a, int b, int c){
    return is_clockwise(a, b, c);
   /* if(a<min(b, c)){
    if(mp.count({a, b, c})) return mp[{a, b, c}];
        else{
            int val=is_clockwise(a, b, c);
            mp[{a, b, c}]=val;
            mp[{a, c, b}]=!val;
            return val;
        }
    }
    else if(b<min(a, c)){
        return is_clock(b, c, a);
    }
    else return is_clock(c, a, b);*/
 
 }
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n=get_n();
 
 
    int v=-1;
 
    for(int i=3; i<=n; i++){
        if(is_clock(1, 2, i)){
            if(v==-1) v=i;
            else if(is_clock(v, 2, i)){
                v=i;
            }
        }
    }
    if(v==-1){
        for(int i=3; i<=n; i++){
            if(is_clock(2, 1, i)){
                if(v==-1) v=i;
                else if(is_clock(v, 1, i)){
                    v=i;
                }
            }
        }
    
        int u=-1;
   
        for(int i=2; i<=n; i++){
            if(i==v||i==1) continue;
            if(is_clock(1, v, i)){
                if(u==-1) u=i;
                else if(is_clock(u, v, i)){
                    u=i;
                }
            }
        }
 
        vector<int> vis(n+1);
        vis[u]=1;
        vis[v]=1;
        int flag=1;
               vector<int> ans;
        ans.push_back(v);
        ans.push_back(u);
        while(flag){
            flag=0;
            for(int i=1; i<=n; i++){
                if(i==u || i==v) continue;
                if(is_clock(v, u, i)){
                    if(flag==0) flag=i;
                    else if(is_clock(flag, u, i)){
                        flag = i;
                    }
                }
            }
                        ans.push_back(flag);
 
            if(vis[flag]||flag==0) break;
            vis[flag] = 1;
            v=u; u=flag;
            
        }
        reverse(ans.begin(), ans.end());
        while(ans.back()!=ans[0]) ans.pop_back();
 
        give_answer(ans.size()-1);;
 
 
    }
    else{
 
        int u=-1;
   
        for(int i=1; i<=n; i++){
            if(i==v||i==2) continue;
            if(is_clock(2, v, i)){
                if(u==-1) u=i;
                else if(is_clock(u, v, i)){
                    u=i;
                }
            }
        }
        
        assert(u!=-1);
        vector<int> vis(n+1);
        vis[u]=1;
        vis[v]=1;
        int flag=1;
               vector<int> ans;
        ans.push_back(v);
        ans.push_back(u);
        while(flag){
            flag=0;
            for(int i=1; i<=n; i++){
                if(i==u || i==v) continue;
                if(is_clock(v, u, i)){
                    if(flag==0) flag=i;
                    else if(is_clock(flag, u, i)){
                        flag = i;
                    }
                }
            }
                        ans.push_back(flag);
 
            if(vis[flag]||flag==0) break;
            vis[flag] = 1;
            v=u; u=flag;
            
        }
        reverse(ans.begin(), ans.end());
        while(ans.back()!=ans[0]) ans.pop_back();
    //Afor(auto i: ans) cout<<i<<" ";
        give_answer(ans.size()-1);;
        
    }
}

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