oj.uz

Submission #294853

# Submission time Handle Problem Language Result Execution time Memory
294853 2020-09-09T10:02:49 Z dandrozavr The Big Prize (IOI17_prize) C++14
97.61 / 100
 85 ms 3032 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 9 ms 404 KB Output is correct
2 Correct 9 ms 408 KB Output is correct
3 Correct 8 ms 400 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 8 ms 392 KB Output is correct
6 Correct 1 ms 396 KB Output is correct
7 Correct 6 ms 416 KB Output is correct
8 Correct 8 ms 412 KB Output is correct
9 Correct 6 ms 412 KB Output is correct
10 Correct 13 ms 480 KB Output is correct

Subtask #2
77.61 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 416 KB Output is correct
2 Correct 8 ms 424 KB Output is correct
3 Correct 10 ms 420 KB Output is correct
4 Correct 9 ms 384 KB Output is correct
5 Correct 8 ms 396 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 7 ms 400 KB Output is correct
8 Correct 9 ms 520 KB Output is correct
9 Correct 8 ms 408 KB Output is correct
10 Correct 5 ms 464 KB Output is correct
11 Correct 13 ms 1580 KB Output is correct
12 Correct 17 ms 1604 KB Output is correct
13 Correct 21 ms 1564 KB Output is correct
14 Correct 20 ms 632 KB Output is correct
15 Correct 53 ms 2948 KB Output is correct
16 Partially correct 38 ms 2824 KB Partially correct - number of queries: 5124
17 Correct 3 ms 420 KB Output is correct
18 Partially correct 53 ms 2888 KB Partially correct - number of queries: 5094
19 Correct 5 ms 416 KB Output is correct
20 Correct 35 ms 1656 KB Output is correct
21 Partially correct 52 ms 2844 KB Partially correct - number of queries: 5084
22 Correct 48 ms 2936 KB Output is correct
23 Correct 12 ms 864 KB Output is correct
24 Correct 13 ms 1384 KB Output is correct
25 Correct 53 ms 2828 KB Output is correct
26 Correct 61 ms 2828 KB Output is correct
27 Correct 8 ms 800 KB Output is correct
28 Correct 49 ms 2764 KB Output is correct
29 Correct 61 ms 2776 KB Output is correct
30 Partially correct 48 ms 2836 KB Partially correct - number of queries: 5068
31 Correct 7 ms 412 KB Output is correct
32 Correct 19 ms 1600 KB Output is correct
33 Correct 1 ms 384 KB Output is correct
34 Partially correct 81 ms 2888 KB Partially correct - number of queries: 5128
35 Correct 13 ms 1028 KB Output is correct
36 Partially correct 82 ms 2916 KB Partially correct - number of queries: 5036
37 Correct 14 ms 1288 KB Output is correct
38 Correct 13 ms 904 KB Output is correct
39 Partially correct 54 ms 2920 KB Partially correct - number of queries: 5039
40 Correct 54 ms 2888 KB Output is correct
41 Partially correct 60 ms 2860 KB Partially correct - number of queries: 5083
42 Partially correct 59 ms 2860 KB Partially correct - number of queries: 5083
43 Correct 58 ms 2916 KB Output is correct
44 Partially correct 56 ms 2832 KB Partially correct - number of queries: 5107
45 Correct 50 ms 2780 KB Output is correct
46 Correct 5 ms 420 KB Output is correct
47 Correct 62 ms 2736 KB Output is correct
48 Partially correct 55 ms 2904 KB Partially correct - number of queries: 5080
49 Partially correct 65 ms 2944 KB Partially correct - number of queries: 5075
50 Partially correct 57 ms 2884 KB Partially correct - number of queries: 5102
51 Partially correct 72 ms 2944 KB Partially correct - number of queries: 5094
52 Partially correct 79 ms 2912 KB Partially correct - number of queries: 5112
53 Correct 12 ms 792 KB Output is correct
54 Partially correct 85 ms 2852 KB Partially correct - number of queries: 5077
55 Correct 6 ms 396 KB Output is correct
56 Partially correct 57 ms 2916 KB Partially correct - number of queries: 5076
57 Partially correct 44 ms 2840 KB Partially correct - number of queries: 5075
58 Partially correct 79 ms 2828 KB Partially correct - number of queries: 5114
59 Partially correct 73 ms 2852 KB Partially correct - number of queries: 5091
60 Partially correct 73 ms 2856 KB Partially correct - number of queries: 5037
61 Correct 13 ms 888 KB Output is correct
62 Correct 12 ms 908 KB Output is correct
63 Correct 8 ms 824 KB Output is correct
64 Correct 10 ms 812 KB Output is correct
65 Correct 5 ms 392 KB Output is correct
66 Correct 4 ms 424 KB Output is correct
67 Correct 9 ms 392 KB Output is correct
68 Correct 7 ms 384 KB Output is correct
69 Correct 5 ms 384 KB Output is correct
70 Correct 10 ms 384 KB Output is correct
71 Partially correct 67 ms 2936 KB Partially correct - number of queries: 5239
72 Correct 18 ms 1660 KB Output is correct
73 Partially correct 57 ms 2856 KB Partially correct - number of queries: 5176
74 Partially correct 56 ms 2832 KB Partially correct - number of queries: 5203
75 Correct 11 ms 888 KB Output is correct
76 Correct 53 ms 2864 KB Output is correct
77 Partially correct 54 ms 3032 KB Partially correct - number of queries: 5196
78 Correct 13 ms 1656 KB Output is correct
79 Correct 42 ms 2784 KB Output is correct
80 Partially correct 40 ms 2936 KB Partially correct - number of queries: 5200
81 Partially correct 68 ms 2944 KB Partially correct - number of queries: 5194
82 Partially correct 69 ms 2936 KB Partially correct - number of queries: 5158
83 Correct 12 ms 888 KB Output is correct
84 Correct 63 ms 2936 KB Output is correct
85 Partially correct 80 ms 2936 KB Partially correct - number of queries: 5217
86 Correct 10 ms 512 KB Output is correct
87 Correct 14 ms 512 KB Output is correct
88 Correct 9 ms 648 KB Output is correct
89 Correct 7 ms 532 KB Output is correct
90 Correct 10 ms 504 KB Output is correct
91 Correct 13 ms 480 KB Output is correct
92 Correct 6 ms 520 KB Output is correct
93 Correct 18 ms 1272 KB Output is correct
94 Correct 16 ms 1552 KB Output is correct
95 Correct 14 ms 1408 KB Output is correct
96 Correct 14 ms 1272 KB Output is correct
97 Correct 9 ms 504 KB Output is correct