oj.uz

Submission #294855

# Submission time Handle Problem Language Result Execution time Memory
294855 2020-09-09T10:03:00 Z dandrozavr The Big Prize (IOI17_prize) C++14
97.61 / 100
 76 ms 3044 KB 
#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define ld long double
#define fi first
#define se second
#define F first
#define S second
#define pii pair < int , int >
#define _ <<" "<<
#define TIME 1.0 * clock() / CLOCKS_PER_SEC


const int N = 2e5 + 2;
int byl[N];
pii ty[N];
bool used[N];
int all = 0;
pii Ask(int i){
    if (used[i]) return ty[i];
    ++all;
//    if (all == 10000){
//        while(true) continue;
//    }
    auto res = ask(i);
    used[i] = 1;
    return make_pair(res[0], res[1]);
}

set < int > ava, del;
vector < int > Del;
vector < int > mark[1001];
void correct(int pos, int last = -1){
//    if (pos == 99999) cerr << last _ byl[pos] _ ty[pos].F _ ty[pos].S << endl;
    if (last == -1){
        if (Del.size() == 0) return;
//        cout << pos _ byl[pos] _ Del.back() << endl;
        for (auto last : Del){
//            cout << last << " ";
            if (last >= byl[pos]) continue;
            int pp = lower_bound(mark[last].begin(), mark[last].end(), pos) - mark[last].begin();
            byl[pos] = last;
            ty[pos] = {ty[pos].F - pp, ty[pos].S - (mark[last].size() - pp)};
//            if (pos == 99999)
//                cerr << last _ pos _ mark[last].size() _ pp _ ty[pos].F _ ty[pos].S << endl;
        }
//        cout<<endl;
        return;
    }
    int pp = lower_bound(mark[last].begin(), mark[last].end(), pos) - mark[last].begin();
    byl[pos] = last;
    ty[pos] = {ty[pos].F - pp, ty[pos].S - (mark[last].size() - pp)};
}


void solve(int l, int r, int nsum){
    if (l + 1 >= r){
        for (; l <= r; ++l){
            if (byl[l]) continue;
            ty[l] = Ask(l);
            byl[l] = ty[l].F + ty[l].S;
        }
        return;
    }
    int mid = (l + r) >> 1;
    int m1 = mid, m2 = mid;
    for (; m1 >= l; --m1){
        ty[m1] = Ask(m1);
        byl[m1] = ty[m1].F + ty[m1].S;
        correct(m1);
        if (byl[m1] == nsum) break;
    }
    for (; m2 <= r; ++m2){
        ty[m2] = Ask(m2);
        byl[m2] = ty[m2].F + ty[m2].S;
        correct(m2);
        if (byl[m2] == nsum) break;
    }
    if (l <= m1 && ty[l].F != ty[m1].F)
        solve(l, m1, nsum);
    if (r >= m2 && ty[r].F != ty[m2].F)
        solve(m2, r, nsum);
}

mt19937_64 gen1(chrono::high_resolution_clock::now().time_since_epoch().count());

int find_best(int n) {
    int bg = 480; // 370
	int cnst1 = min(n, bg);
	int cnst2 = min(n, bg);
    int mx = -1;
	for (int i = 0; i < cnst1; ++i){
        auto res = Ask(i);
        int sum = res.F + res.S;
        if (sum == 0) return i;
        ava.insert(sum);
        byl[i] = sum;
        ty[i] = res;
        mx = max(mx, sum);
        if (sum > bg) break;
    }
    for (int i = n - 1; i >= n - cnst2; --i){
        auto res = Ask(i);
        int sum = res.F + res.S;
        if (sum == 0) return i;
        ava.insert(sum);
        byl[i] = sum;
        ty[i] = res;
        if (sum > bg || sum == mx) break;
    }
    int last = -1;
    while(true){
        if (ava.size() == 0) break;
        int x = (*ava.rbegin());
//        cout << ava.size() _ x _ byl[99999] << endl;
        del.insert(x);
        Del.pb(x);
        ava.erase(x);
        for (int i = 0; i < n; ++i)
            if (byl[i] == x){
                mark[x].pb(i);
            }
        for (int i = 0; i < n; ++i)
            if (byl[i] > x){
                correct(i, x);
            }

        int lef = n + 1, rig = - 1;
        for (int i = 0; i < n; ++i)
            if (byl[i] == x){
                if (lef == n + 1) lef = i;
                rig = i;
            }
//        cerr << x _ lef _ rig _ all << endl;
        if (lef >= rig){
            cout << "BUG" << endl;
            exit(0);
        }
        solve(lef, rig, x);
        last = x;
        for (int i = 0; i < n; ++i){
            if (byl[i] && !del.count(byl[i]) && !ava.count(byl[i])){
                ava.insert(byl[i]);
//                cout << i _ byl[i] << "\n";
            }
        }
//        cout<<endl;
    }
    int ans = -1, cnt = 0;
    for (int i = 0; i < n; ++i)
    if (byl[i] == 0 && used[i]){
//        cout << i << endl;
        ++cnt;
        ans = i;
    }

    if (cnt != 1){
        cout << "CNT bug" << cnt << endl;
    }
    return ans;
}

Compilation message

prize.cpp: In function 'int find_best(int)':
prize.cpp:113:9: warning: variable 'last' set but not used [-Wunused-but-set-variable]
  113 |     int last = -1;
      |         ^~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 392 KB Output is correct
2 Correct 10 ms 412 KB Output is correct
3 Correct 8 ms 396 KB Output is correct
4 Correct 9 ms 384 KB Output is correct
5 Correct 10 ms 412 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 7 ms 424 KB Output is correct
8 Correct 14 ms 424 KB Output is correct
9 Correct 14 ms 400 KB Output is correct
10 Correct 9 ms 428 KB Output is correct

Subtask #2
77.61 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 420 KB Output is correct
2 Correct 7 ms 408 KB Output is correct
3 Correct 7 ms 416 KB Output is correct
4 Correct 5 ms 388 KB Output is correct
5 Correct 8 ms 416 KB Output is correct
6 Correct 1 ms 388 KB Output is correct
7 Correct 8 ms 420 KB Output is correct
8 Correct 9 ms 416 KB Output is correct
9 Correct 8 ms 392 KB Output is correct
10 Correct 10 ms 440 KB Output is correct
11 Correct 16 ms 1548 KB Output is correct
12 Correct 20 ms 1620 KB Output is correct
13 Correct 19 ms 1656 KB Output is correct
14 Correct 20 ms 696 KB Output is correct
15 Correct 32 ms 2940 KB Output is correct
16 Partially correct 70 ms 2904 KB Partially correct - number of queries: 5124
17 Correct 5 ms 384 KB Output is correct
18 Partially correct 67 ms 2828 KB Partially correct - number of queries: 5094
19 Correct 5 ms 384 KB Output is correct
20 Correct 42 ms 1672 KB Output is correct
21 Partially correct 68 ms 2848 KB Partially correct - number of queries: 5084
22 Correct 45 ms 2916 KB Output is correct
23 Correct 9 ms 920 KB Output is correct
24 Correct 17 ms 1400 KB Output is correct
25 Correct 61 ms 2864 KB Output is correct
26 Correct 49 ms 2804 KB Output is correct
27 Correct 8 ms 928 KB Output is correct
28 Correct 62 ms 2784 KB Output is correct
29 Correct 55 ms 2772 KB Output is correct
30 Partially correct 33 ms 2844 KB Partially correct - number of queries: 5068
31 Correct 6 ms 396 KB Output is correct
32 Correct 11 ms 1688 KB Output is correct
33 Correct 1 ms 384 KB Output is correct
34 Partially correct 76 ms 2908 KB Partially correct - number of queries: 5128
35 Correct 12 ms 1052 KB Output is correct
36 Partially correct 35 ms 2840 KB Partially correct - number of queries: 5036
37 Correct 15 ms 1280 KB Output is correct
38 Correct 15 ms 904 KB Output is correct
39 Partially correct 66 ms 3012 KB Partially correct - number of queries: 5039
40 Correct 50 ms 2816 KB Output is correct
41 Partially correct 75 ms 2844 KB Partially correct - number of queries: 5083
42 Partially correct 76 ms 2912 KB Partially correct - number of queries: 5083
43 Correct 66 ms 2844 KB Output is correct
44 Partially correct 45 ms 2896 KB Partially correct - number of queries: 5107
45 Correct 51 ms 2772 KB Output is correct
46 Correct 6 ms 392 KB Output is correct
47 Correct 59 ms 2720 KB Output is correct
48 Partially correct 63 ms 2896 KB Partially correct - number of queries: 5080
49 Partially correct 52 ms 2936 KB Partially correct - number of queries: 5075
50 Partially correct 69 ms 2936 KB Partially correct - number of queries: 5102
51 Partially correct 46 ms 2908 KB Partially correct - number of queries: 5094
52 Partially correct 35 ms 2828 KB Partially correct - number of queries: 5112
53 Correct 12 ms 904 KB Output is correct
54 Partially correct 34 ms 2840 KB Partially correct - number of queries: 5077
55 Correct 5 ms 388 KB Output is correct
56 Partially correct 40 ms 2832 KB Partially correct - number of queries: 5076
57 Partially correct 46 ms 2828 KB Partially correct - number of queries: 5075
58 Partially correct 63 ms 2832 KB Partially correct - number of queries: 5114
59 Partially correct 51 ms 2896 KB Partially correct - number of queries: 5091
60 Partially correct 58 ms 3000 KB Partially correct - number of queries: 5037
61 Correct 12 ms 888 KB Output is correct
62 Correct 12 ms 896 KB Output is correct
63 Correct 12 ms 896 KB Output is correct
64 Correct 7 ms 824 KB Output is correct
65 Correct 5 ms 384 KB Output is correct
66 Correct 5 ms 384 KB Output is correct
67 Correct 12 ms 320 KB Output is correct
68 Correct 5 ms 384 KB Output is correct
69 Correct 4 ms 384 KB Output is correct
70 Correct 8 ms 384 KB Output is correct
71 Partially correct 50 ms 2844 KB Partially correct - number of queries: 5239
72 Correct 17 ms 1656 KB Output is correct
73 Partially correct 52 ms 2936 KB Partially correct - number of queries: 5176
74 Partially correct 58 ms 2996 KB Partially correct - number of queries: 5203
75 Correct 11 ms 896 KB Output is correct
76 Correct 49 ms 2948 KB Output is correct
77 Partially correct 51 ms 3044 KB Partially correct - number of queries: 5196
78 Correct 14 ms 1664 KB Output is correct
79 Correct 33 ms 2808 KB Output is correct
80 Partially correct 57 ms 2936 KB Partially correct - number of queries: 5200
81 Partially correct 48 ms 2936 KB Partially correct - number of queries: 5194
82 Partially correct 64 ms 2936 KB Partially correct - number of queries: 5158
83 Correct 10 ms 896 KB Output is correct
84 Correct 31 ms 2944 KB Output is correct
85 Partially correct 56 ms 2936 KB Partially correct - number of queries: 5217
86 Correct 10 ms 512 KB Output is correct
87 Correct 11 ms 512 KB Output is correct
88 Correct 11 ms 512 KB Output is correct
89 Correct 8 ms 512 KB Output is correct
90 Correct 9 ms 504 KB Output is correct
91 Correct 8 ms 640 KB Output is correct
92 Correct 6 ms 556 KB Output is correct
93 Correct 16 ms 1276 KB Output is correct
94 Correct 17 ms 1528 KB Output is correct
95 Correct 15 ms 1400 KB Output is correct
96 Correct 13 ms 1272 KB Output is correct
97 Correct 10 ms 512 KB Output is correct