Submission #1225155

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225155		dosts	Triangles (CEOI18_tri)	C++20	55 / 100	570 ms	920 KiB

tri

#include <bits/stdc++.h>
#include "trilib.h"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e9;

const int N = 1e5+1;

void solve() {
    int n = get_n();
    vi poly = {1,2,3};
    if (!is_clockwise(1,2,3)) reverse(all(poly));
    int h = 3;
    for (int i=4;i<=n;i++) {
        vi low;
        for (int j = 0;j<h;j++) {
            if (!is_clockwise(i,poly[j],poly[(j+1)%h])) low.push_back(j);
        }
        if (low.empty()) continue;
        int con = -1,con2 = -1;
        for (int j = 0;j<big(low);j++) {
            int nxt = poly[(low[j]+1)%h];
            int prv = poly[(low[j]+h-1)%h];
            int ths = poly[low[j]];
            if (is_clockwise(i,nxt,ths) && 
                !is_clockwise(i,ths,prv)) con = ths;
        }
        for (int j = big(low)-1;j>=0;j--) {
            int nxt = poly[(low[j]+2)%h];
            int prv = poly[low[j]%h];
            int ths = poly[(low[j]+1)%h];
            if (!is_clockwise(i,prv,ths) && 
                is_clockwise(i,ths,nxt)) con2 = ths;
        }
        assert(con != -1 && con2 != -1);
        vi to_del;
        int p = find(all(poly),con)-poly.begin();
        for (int j = (p+1)%h;poly[j] != con2;j=(j+1)%h) to_del.push_back(poly[j]);
        for (auto it : to_del) poly.erase(find(all(poly),it));
        poly.insert(find(all(poly),con)+1,i);
        h = big(poly);
    }
    give_answer(h);
} 

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifdef Dodi
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}

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