Submission #950568

#	Time	Username	Problem	Language	Result	Execution time	Memory
950568		berr	Triangles (CEOI18_tri)	C++17	0 / 100	1 ms	348 KiB

tri

#include <bits/stdc++.h>
using namespace std;
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "trilib.h"

map<array<int, 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){
    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[{b, c, a}]=val;
        mp[{c, a, b}]=val;
        mp[{c, b, a}]=!val;
        mp[{b, a, c}]=!val;
        mp[{a, c, b}]=!val;
        return val;
    }

 }
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=v; v=2;
        swap(u, v);
        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=v; v=1;
        swap(u, v);
        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: 0 / 15
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 25