Submission #397261

#	Time	Username	Problem	Language	Result	Execution time	Memory
397261		idk321	The Big Prize (IOI17_prize)	C++11	0 / 100	38 ms	11244 KiB

prize

#include "prize.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;


vector<int> big;

pair<int, vector<int>> differentRight(int a, int b, vector<int> inf)
{

    int res = -1;
    vector<int> rinf;
    while (a <= b)
    {
        int mid = (a + b) / 2;
        vector<int> cinf = ask(mid);

        if (cinf == inf)
        {
            a = mid + 1;
        } else
        {
            res = mid;
            rinf = cinf;
            b = mid - 1;
        }
    }

    return {res, rinf};
}

pair<int, vector<int>> differentLeft(int a, int b, vector<int> inf)
{
    int res = -1;
    vector<int> rinf;
    while (a <= b)
    {
        int mid = (a + b) / 2;
        vector<int> cinf = ask(mid);

        if (cinf == inf)
        {
            b = mid - 1;
        } else
        {
            res = mid;
            rinf = cinf;
            a = mid + 1;
        }
    }

    return {res, rinf};
}

int find_best(int N) {
    n = N;


    if (n <= 5000)
    {
        int res = -1;
        for (int i = 0; i < n; i++)
        {
            vector<int> v = ask(i);
            if (v[0] == 0 && v[1] == 0) res = i;
        }

        return res;
    }

    vector<int> needed = {0, 0};
    big = {0, 0};
    vector<int> inf;
    int cur = 0;
    inf = ask(cur);
    if (inf[0] + inf[1] > big[0] + big[1]) big = inf;

    if (inf == needed) return cur;
    for (int i = 0; i < 4; i++)
    {
        auto p1 = differentRight(cur, n - 1, inf);
        cur = p1.first;
        if (cur == -1) break;
        inf = p1.second;
        if (inf[0] + inf[1] > big[0] + big[1]) big = inf;
    }
    int sum = big[0] + big[1];

    vector<vector<int>> infAt(n, vector<int>(2));
    for (int i = 0; i < n; i += 100)
    {
        infAt[i] = ask(i);
        if (infAt[i] == needed) return i;
    }

    for (int i = 0; i + 100 < n; i += 100)
    {
        int l = i;
        int r = i + 100;

        if (infAt[l] == needed) return l;
        if (infAt[r] == needed) return r;

        if (infAt[l][0] + infAt[l][1] == sum)
        {
            auto p1 = differentRight(l, r, infAt[l]);
            l = p1.first;

            if (l != -1)infAt[l] = p1.second;
        }
        if (infAt[r][0] + infAt[r][1] == sum)
        {
            auto p2 = differentLeft(l, r, infAt[r]);
            r = p2.first;
            if (r != -1) infAt[r] = p2.second;
        }


        if (l != -1 && infAt[l] == needed) return l;
        if (r != -1 && infAt[r] == needed) return r;

        if (l == -1 || r == -1) continue;

        if (r - l <= 1) continue;
        if ((infAt[l][0] + infAt[l][1] == infAt[r][0] + infAt[r][1] &&  infAt[l][1] - infAt[r][1] > 0) || (infAt[l][0] + infAt[l][1] <= 30 || infAt[r][0] + infAt[r][1] <= 30))
        {
            for (int j = l + 1; j < r; j++)
            {
                vector<int> cinf = ask(j);
                if (cinf[0] == 0 && cinf[1] == 0) return j;
            }
        }
    }

    for (int i = 0; i < n; i += 100)
    {
        if (i + 100 >= n)
        {
            for (int j = i + 1; j < n; j++)
            {
                vector<int> cinf = ask(j);
                if (cinf == needed) return j;
            }
        }
    }


	return 0;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 80