Submission #321604

#	Time	Username	Problem	Language	Result	Execution time	Memory
321604		12tqian	The Big Prize (IOI17_prize)	C++17	20 / 100	335 ms	19692 KiB

prize

#include "prize.h"
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;

using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define f first
#define s second
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()

mt19937 rng((uint32_t) chrono::steady_clock::now().time_since_epoch().count());

int find_best(int n) {
	int queries = 0;
	auto query = [&](int id) -> vector<int> {
		queries++;
		assert(queries <= 9990);
		return ask(id);
	};
    if (n <= 7) {
            for(int i = 0; i < n; i++) {
            std::vector<int> res = query(i);
            if(res[0] + res[1] == 0)
                return i;
        }
    }
    const int TIMES = 30;
    int lim  = 0;
    for (int i = 0; i < TIMES; i++) {
        vector<int> q = query(rng() % n);
        lim = max(lim, q[0] + q[1]);
    }
    Tree<int> rem; // not identified
    Tree<int> done;
    for (int i = 0; i < n; i++) {
        rem.insert(i);
    }
	auto purge = [&](int id) {
		rem.erase(id);
		done.insert(id);
	};
	auto destroy = [&](int id, int t) {
		if (t == 0) {
			while (sz(rem) && *rem.begin() < id) purge(*rem.begin());
		} else {
			while (sz(rem) && *rem.rbegin() < id) purge(*rem.rbegin());
		}
	};
    while (true) {
        bool ok = false;
        int lo = 0;
        int hi = sz(rem) - 1;
        while (hi - lo > 1) {
            int mid = (lo + hi) / 2;
            int id = *rem.find_by_order(mid);
            vector<int> q = query(id);
            if (q[0] + q[1] == 0) {
                return id;
            } else if (q[0] + q[1] < lim) {
                purge(id);
				for (int t = 0; t < 2; t++) {
					if (q[t] == 0) destroy(id, t);
				}
                ok = true;
                break;
            } else {
                q[0] -= done.order_of_key(id);
                q[1] -= sz(done) - done.order_of_key(id);
				if (q[0] && q[1]) {
					if (q[0] > q[1]) hi = mid - 1;
					else lo = mid + 1;
				} else if (q[0]) {
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            }
        }
        if (ok) continue;
        int id = *rem.find_by_order(lo);
        vector<int> q = query(id);
        if (q[0] + q[1] < lim) {
            if (q[0] + q[1] == 0) {
                return id;
            } else {
                purge(id);
				for (int t = 0; t < 2; t++) {
					if (q[t] == 0) destroy(id, t);
				}
            }
        } else {
            id = *rem.find_by_order(hi);
            q = query(id);
            assert(q[0] + q[1] < lim);
            if (q[0] + q[1] == 0) {
                return id;
            } else {
                purge(id);
				for (int t = 0; t < 2; t++) {
					if (q[t] == 0) destroy(id, t);
				}
            }
        }
    }
	return 0;
}

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