oj.uz

답안 #1065403

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1065403 2024-08-19T07:04:49 Z mc061 커다란 상품 (IOI17_prize) C++17
20 / 100
 60 ms 2416 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -