Submission #116724

#	Time	Username	Problem	Language	Result	Execution time	Memory
116724		johutha	Triangles (CEOI18_tri)	C++14	0 / 100	3 ms	384 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);

    if (is_clockwise(1, 2, 3))
    {
        next[0] = 1;
        next[1] = 2;
        next[2] = 0;
    }
    else
    {
        next[0] = 2;
        next[1] = 0;
        next[2] = 1;
    }
    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;

                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;
                        if (old == start) start = i;
                    }
                }
                break;
            }
            else
            {
                curr = next[curr];
            }
        }
    }
    /*int curr = -1;
    while (curr != start)
    {
        if (curr == -1) curr = start;
        cout << curr << " ";
        curr = next[curr];
    }*/
    int res = 0;
    for (int i : next)
    {
        if (i != -1) res++;
    }
    give_answer(res);
}

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