Submission #572094

#	Time	Username	Problem	Language	Result	Execution time	Memory
572094		piOOE	Triangles (CEOI18_tri)	C++17	20 / 100	1 ms	468 KiB

tri

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

using namespace std;

#define sz(x) ((int)size(x))
#define all(x) begin(x), end(x)
#define trace(x) cout << #x << ": " << (x) << endl;

typedef long long ll;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }

const int N = 40000;
const ll infL = 3e18;

int n;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    n = get_n();
    int cnt = 0;
    for (int s = 0; s < n; ++s) {
        //pseudo Jarvis algorithm
        int uu = -1;
        int p0 = s, pi = s;
        int k = 0;
        vector<bool> used(n);
        vector<int> p(n, -1);
        do {
            used[p0] = true;
            pi = -1;
            for (int i = 0; i < n; ++i) {
                if (p0 != i && pi != -1) {
                    assert(cnt < 1000000);
                    ++cnt;
                    if (is_clockwise(p0 + 1, pi + 1, i + 1))
                        pi = i;
                } else if (p0 != i) {
                    pi = i;
                }
            }
            p[pi] = p0;
            p0 = pi;
            if (uu == -2) {
                uu = pi;
            }
            if (uu == -1) {
                uu = -2;
            }
        } while (!used[pi]);
        fill(all(used), false);
        do {
            ++k;
            used[pi] = true;
            pi = p[pi];
        } while (pi != p0);
        assert(uu >= 0 && used[uu]);
        give_answer(k);
        return 0;
    }
    return 0;
}

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