Submission #1065403

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1065403	2024-08-19T07:04:49 Z	mc061	The Big Prize (IOI17_prize)	C++17	20 / 100	60 ms	2416 KB

prize

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

const int N = 2e5+6;
bool is_worst[N]={};
bool know[N]={};
pair<int, int> val[N];

unordered_map<int, set<int, greater<int>>> last_by_sum;

vector<int> ask(int i);

pair<int, int> get(int i) {
    if (know[i]) {
        return val[i];
    }
    know[i] = true;
    auto now = ask(i);
    val[i].first = now[0], val[i].second = now[1];
    last_by_sum[now[0] + now[1]].insert(i);
    return {now[0], now[1]};
}

int find_best(int n) {
    int mx = 0;
    for (int i = 0; i < min(n, 550); ++i) {
        auto now = get(i);
        val[i].first = now.first;
        val[i].second = now.second;
        mx = max(mx, val[i].first + val[i].second);
        last_by_sum[val[i].first + val[i].second].insert(i);
        if (val[i].first + val[i].second == 0) return i; 
    }
    for (int i = 0; i < min(n, 550); ++i) {
        if (val[i].first + val[i].second == mx) {
            is_worst[i] = true;
            know[i] = true;
        }
        if (val[i].first + val[i].second == 0) return i;
    }
    int l = 550;
    while (true) {
        auto now = get(l);
        last_by_sum[now.first + now.second].insert(l);
        val[l] = {now.first, now.second};
        
        if (now.first + now.second == mx) break;
        ++l;
    }
    while (true) {
        int low = l, high = n-1;
        while (high != low) {
            int mid = (high + low + 1) >> 1;
            auto now = get(mid);
            int sum = now.first + now.second;
            if (sum == mx) {
                if (now.first == val[l].first) {
                    low = mid+1;
                }
                else {
                    high = mid-1;
                }
                continue;
            }
            if (now.first + now.second == 0) return mid;
            int v = mid;
            bool worth_left = true;
            while (sum < mx && worth_left) {
                --v;
                now = get(v);
                sum = now.first + now.second;
                set<int, greater<int>>& s = last_by_sum[sum];
                auto it = s.upper_bound(v);
                if (it != s.end()) {
                    if (val[v].first == val[*it].first) {
                        worth_left = false;
                        break;
                    }
                }
                if (sum == 0) return v;
            }
            if (!worth_left) {
                int v = mid;
                while (sum < mx) {
                    ++v;
                    now = get(v);
                    sum = now.first + now.second;
                    if (sum == 0) return v;
                }
                l = v;
                break;
            }
            if (now.first == val[l].first) {
                int v = mid;
                while (sum < mx) {
                    ++v;
                    now = get(v);
                    sum = now.first + now.second;
                    if (sum == 0) return v;
                }
                l = v;
                break;
            }
            high = v-1;
        }
        auto x = get(low);
        if (x.first + x.second == 0) return low;
        l = low+1;
        get(l);
        int sum = val[l].first + val[l].second;
        if (sum == 0) return l;
        while (sum < mx) {
            ++l;
            get(l);
            sum = val[l].first + val[l].second;
            if (sum == 0) return l;
        }
    }
}

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	344 KB	Output is correct
2	Correct	4 ms	600 KB	Output is correct
3	Correct	3 ms	440 KB	Output is correct
4	Correct	3 ms	344 KB	Output is correct
5	Correct	4 ms	600 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Correct	3 ms	416 KB	Output is correct
8	Correct	2 ms	344 KB	Output is correct
9	Correct	4 ms	344 KB	Output is correct
10	Correct	3 ms	344 KB	Output is correct

Subtask #2

0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	344 KB	Output is correct
2	Correct	3 ms	452 KB	Output is correct
3	Correct	4 ms	344 KB	Output is correct
4	Correct	3 ms	460 KB	Output is correct
5	Correct	3 ms	344 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Correct	4 ms	468 KB	Output is correct
8	Correct	3 ms	344 KB	Output is correct
9	Correct	3 ms	344 KB	Output is correct
10	Correct	4 ms	344 KB	Output is correct
11	Correct	7 ms	856 KB	Output is correct
12	Correct	4 ms	476 KB	Output is correct
13	Correct	5 ms	1368 KB	Output is correct
14	Correct	3 ms	344 KB	Output is correct
15	Correct	12 ms	1368 KB	Output is correct
16	Partially correct	37 ms	2384 KB	Partially correct - number of queries: 8975
17	Correct	2 ms	344 KB	Output is correct
18	Incorrect	60 ms	2416 KB	Incorrect
19	Halted	0 ms	0 KB	-