Submission #362080

#	Time	Username	Problem	Language	Result	Execution time	Memory
362080		idk321	Jousting tournament (IOI12_tournament)	C++11	0 / 100	1079 ms	2028 KiB

tournament

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

const int N = 5005;
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];
}

int kth(int k, int a, int b, int node)
{
    if (a == b) return a;

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


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


    int best = 0;
    //cout << endl;
    for (int i = 0; i < n; i++)
    {
        vector<int> nr(n);
        nr[i] = r;
        for (int j = 0; j < n - 1; j++)
        {
            if (j < i) nr[j] = k[j];
            else nr[j + 1] = k[j];
        }
        for (int i = 0; i < n; i++) make(i, 1, 0, n - 1, 1);
        int cur = 0;
        vector<int> ok(n, 1);
        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);
                int ki = 0;
                int passed = 0;
                for (int m = 0; m < n; m++)
                {
                    if (ok[m]) passed++;
                    if (passed > s[j])
                    {
                        ki = m;
                        break;
                    }
                }
                if (nr[ki] > cbest)
                {
                    cbest = nr[ki];
                    ci = ki;
                }
                ok[ki] = 0;
                make(ki, 0, 0, n - 1, 1);
            }
            ok[ci] = 1;
            make(ci, 1, 0, n - 1, 1);
            //cout << i << " " << cbest << endl;
            if (cbest == r) cur++;
        }

        //cout << i << " " << cur << endl;
        best = max(best, cur);
    }

  return best;

}

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

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