Submission #362089

#	Time	Username	Problem	Language	Result	Execution time	Memory
362089		idk321	Jousting tournament (IOI12_tournament)	C++11	17 / 100	1096 ms	1644 KiB

tournament

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

const int N = 5000;
int nr[N];
int tree[4 * N];

void make(int i, int num, int a, int b, int node)
{
    if (a == b)
    {
        tree[node] = num;
        return;
    }

    int mid = (a + b) / 2;
    if (i <= mid) make(i, num, a, mid, node * 2);
    else make(i, num, mid + 1, b, node * 2 + 1);
    tree[node] = tree[node * 2] + tree[node * 2  + 1];
}

void cons(int a, int b, int node)
{
    if (a == b)
    {
        tree[node] = 1;
        return;
    }

    int mid = (a + b) / 2;
    cons(a, mid, node * 2);
    cons(mid + 1, b, node * 2 + 1);
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

int kth(int k, int a, int b, int node)
{
    if (a == b)
    {
        tree[node] = 0;
        return a;
    }

    int mid = (a + b) / 2;
    int ret = -1;
    if (tree[node * 2] > k) ret = kth(k, a, mid, node * 2);
    else ret = kth(k - tree[node * 2], mid + 1, b, node * 2 + 1);
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
    return ret;
}


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


    int best = -1;
    int pos = -1;
    //cout << endl;
    for (int i = 0; i < n; i++)
    {
        nr[i] = r;
        for (int j = 0; j < n - 1; j++)
        {
            if (j < i) nr[j] = k[j];
            else nr[j + 1] = k[j];
        }
        cons(0, n - 1, 1);
        int cur = 0;
        for (int j = 0; j < c; j++)
        {
            int ci = -1;
            int cbest = -1;
            for (int l = s[j]; l <= e[j]; l++)
            {
                int ki = kth(s[j], 0, n - 1, 1);
                if (nr[ki] > cbest)
                {
                    cbest = nr[ki];
                    ci = ki;
                }
            }
            make(ci, 1, 0, n - 1, 1);
            if (cbest == r) cur++;
        }

        //cout << cur << endl;
        if (cur > best)
        {
            best = cur;
            pos = i;
        }
    }

  return pos;

}

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

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