Submission #362121

#	Time	Username	Problem	Language	Result	Execution time	Memory
362121		idk321	Jousting tournament (IOI12_tournament)	C++11	49 / 100	112 ms	2668 KiB

tournament

#include <bits/stdc++.h>
using namespace std;

const int N = 5000;

struct Node
{
    Node* next;
    int l;
    int r;

    Node(int l1, int r1)
    {
        l = l1;
        r = r1;
        next = nullptr;
    }
};

vector<int> pref;

int go(Node* cur)
{
    int sum = pref[cur->r];
    if (cur->l != 0) sum -= pref[cur->l - 1];
    if (sum != 0) return 0;
    int res = 1;
    if (cur->next != nullptr) res += go(cur->next);
    return res;
}

Node* first[N];

int GetBestPosition(int n, int c, int r, int *k, int *s, int *e) {


    for (int i = 0; i < n; i++)
    {
        first[i] = new Node(i, i);
    }
    vector<Node*> cur(first, first + N);
    for (int i = 0; i < c; i++)
    {
        Node* next = new Node(cur[s[i]]->l, cur[e[i]]->r);
        for (int l = s[i]; l <= e[i]; l++)
        {
            cur[l]->next = next;
        }
        cur.erase(cur.begin() + s[i], cur.begin() + e[i] + 1);
        cur.insert(cur.begin() + s[i], next);
    }

    int pos = -1;
    int best = -1;
    for (int i = 0; i < n; i++)
    {
        vector<int> order(n);
        pref.resize(n);
        pref.clear();
        order[i] = r;
        for (int j = 0; j < n - 1; j++)
        {
            if (j < i) order[j] = k[j];
            else order[j + 1] = k[j];
        }
        for (int j = 0; j < n; j++)
        {
            if (order[j] <= r) order[j] = 0;
            else order[j] = 1;
        }
        pref[0] = order[0];
        for (int i = 1; i < n; i++)
        {
            pref[i] += pref[i - 1] + order[i];
        }

        int cres = go(first[i]) - 1;
        if (cres > best)
        {
            best = cres;
            pos = i;
        }
    }


    return pos;
}

/*
5 3 2
1
0
4
3
0 1
0 1
0 2
*/

• Subtask 1: 17 / 17
• Subtask 2: 32 / 32
• Subtask 3: 0 / 51