제출 #444169

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
444169		Haruto810198	Triangles (CEOI18_tri)	C++17	100 / 100	309 ms	1636 KiB

tri

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

using namespace std;

#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = 2147483647;
const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;

const int MAX = 40010;

int n;
vi CH;

signed main(){

    //ios_base::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);

    n = get_n();

    if( is_clockwise(1, 2, 3) ){
        CH = {1, 2, 3};
    }
    else{
        CH = {1, 3, 2};
    }

    FOR(i, 4, n, 1){

        int V = szof(CH);
        set<int> inv_edge;

        if( !is_clockwise(CH[V-1], CH[0], i) ){
            inv_edge.insert(V-1);
        }
        else{
            int L = 0, R = V-1, mid;
            while(L + 1 < R){
                mid = (L + R) / 2;
                if( is_clockwise(CH[L], CH[mid], i) ){
                    L = mid;
                }
                else{
                    R = mid;
                }
            }

            if( !is_clockwise(CH[L], CH[R], i) ){
                inv_edge.insert(L);
            }

        }

        if(inv_edge.empty()){
            continue;
        }

        int E = *inv_edge.begin();
        while( !is_clockwise(CH[E], CH[(E+1)%V], i) ){
            inv_edge.insert(E);
            E = (E+1) % V;
        }

        E = *inv_edge.begin();
        while( !is_clockwise(CH[E], CH[(E+1)%V], i) ){
            inv_edge.insert(E);
            E = (E-1+V) % V;
        }

        if(szof(inv_edge)==1){
            auto it = CH.begin() + (*inv_edge.begin()) + 1;
            CH.insert(it, i);
            continue;
        }

        bool vis = 0;
        for(int j : inv_edge){
            if(inv_edge.find((j+1)%V) != inv_edge.end()){
                CH[(j+1)%V] = -1;
                if(vis == 0){
                    vis = 1;
                    CH[(j+1)%V] = i;
                }
            }
        }

        vi tmp;
        for(int j : CH){
            if(j != -1){
                tmp.pb(j);
            }
        }

        CH = tmp;

    }

    give_answer(szof(CH));

    return 0;

}

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