Submission #117085

#	Time	Username	Problem	Language	Result	Execution time	Memory
117085		johutha	Triangles (CEOI18_tri)	C++14	55 / 100	670 ms	1152 KiB

tri

#include "trilib.h"
#include <vector>
#include <algorithm>
#include <iostream>

#define int int64_t

using namespace std;

signed main()
{
    int n = get_n();

    vector<int> next(n, -1);
    vector<int> prev(n, -1);

    if (is_clockwise(1, 2, 3))
    {
        next[0] = 1;
        next[1] = 2;
        next[2] = 0;
        prev[0] = 2;
        prev[1] = 0;
        prev[2] = 1;
    }
    else
    {
        next[0] = 2;
        next[1] = 0;
        next[2] = 1;
        prev[0] = 1;
        prev[1] = 2;
        prev[2] = 0;
    }
    int start = 0;
    for (int i = 3; i < n; i++)
    {
        int curr = -1;
        while (curr != start)
        {
            if (curr == -1)
            {
                curr = start;
            }
            bool cl = is_clockwise(curr + 1, i + 1, next[curr] + 1);
            if (cl)
            {
                next[i] = next[curr];
                next[curr] = i;
                prev[i] = curr;
                prev[next[i]] = i;

                while (true)
                {
                    if (is_clockwise(i + 1, next[i] + 1, next[next[i]] + 1)) break;
                    else
                    {
                        int old = next[i];
                        next[i] = next[next[i]];
                        next[old] = -1;
                        prev[next[i]] = i;
                        prev[old] = -1;
                        if (old == start) start = i;
                    }
                }

                while (true)
                {
                    if (!is_clockwise(i + 1, prev[i] + 1, prev[prev[i]] + 1)) break;
                    else
                    {
                        int old = prev[i];
                        prev[i] = prev[prev[i]];
                        prev[old] = -1;
                        next[prev[i]] = i;
                        next[old] = -1;
                        if (old == start) start = i;
                    }
                }
                break;
            }
            else
            {
                curr = next[curr];
            }
        }
        /*
        cout << i << ":\n";
        int cn = -1;
        while (cn != start)
        {
            if (cn == -1) cn = start;
            cout << cn << " ";
            cn = next[cn];
        }
        cout << "\n";
        */
    }
    int res = 0;
    for (int i : next)
    {
        if (i != -1) res++;
    }
    give_answer(res);
}

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