# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
789897 | 2023-07-22T06:55:19 Z | lollipop | The Big Prize (IOI17_prize) | C++17 | 1000 ms | 5324 KB |
#include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/rope> //#define int long long #define pb push_back #define s second #define f first #define pf push_front #define inf 100000000000000000 #define bitebi __builtin_popcountll #define FOR( i , n ) for( int i = 0 ; i < n ; i ++ ) #define YES cout <<"YES\n" #define NO cout << "NO\n" #define debug cout << "Here Fine" << endl ; #define pr pair < int , int > #define fbo find_by_order // returns iterator #define ook order_of_key // returns strictly less numbers than key using namespace std ; //#pragma GCC optimize("Ofast") //#pragma GCC target("avx,avx2,fma") using namespace __gnu_pbds; using namespace __gnu_cxx; #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> const double Pi=acos(-1.0); const double EPS=1E-8; const int mod = 1000000007 ; const int mod1 = 998244353 ; const int N = 2e5 + 10 ; mt19937 R(time(0)); map < int , int > ma , ma1 ; #include "prize.h" //static const int max_q = 10000; //static int n; //static int query_count = 0; //static vector<int> g; //static vector<vector<int> > rank_count; // //vector<int> ask(int i) { // query_count++; // if(query_count > max_q) { // cerr << "Query limit exceeded" << endl; // exit(0); // } // // if(i < 0 || i >= n) { // cerr << "Bad index: " << i << endl; // exit(0); // } // // vector<int> res(2); // res[0] = rank_count[g[i] - 1][i + 1]; // res[1] = rank_count[g[i] - 1][n] - res[0]; // return res; //} vector < int > qu[ N ] ; int been[ N ] ; int find_best(int n){ int mx = 0 ; vector < int > pas ; FOR( i , 480 ){ pas = ask( i ) ; if( pas[ 0 ] + pas[ 1 ] == 0 ) return i ; mx = max( mx , pas[ 0 ] + pas[ 1 ] ) ; } vector < pair < int , int > > v ; FOR( i , mx ) v.pb( { 0 , n - 1 } ) ; while( true ){ int cc = 0 ; FOR( i , v.size() ){ if( been[ i ] == 1 ){ cc ++ ; continue ; } int mid = ( v[ i ].f + v[ i ].s ) / 2 ; if( qu[ mid ].size() == 0 ) pas = ask( mid ) ; else pas = qu[ mid ] ; qu[ mid ] = pas ; if( pas[ 1 ] + pas[ 0 ] == 0 ) return mid ; if( v[ i ].f == v[ i ].s ) been[ i ] = 1 ; if( pas[ 1 ] < ( v.size() - i - 1 ) ){ v[ i ].s = mid - 1 ; continue ; } if( pas[ 1 ] < ( v.size() - i ) ) v[ i ].s = mid ; else v[ i ].f = mid + 1 ; } // if( cc == v.size() ) return 0 ; } } //int main() { // cin >> n; // // g.resize(n); // for(int i = 0; i < n; i++) { // cin >> g[i]; // if(g[i] < 1) { // cerr << "Invalid rank " << g[i] << " at index " << i << endl; // exit(0); // } // } // // int max_rank = *max_element(g.begin(), g.end()); // // rank_count.resize(max_rank + 1, vector<int>(n + 1, 0)); // for(int r = 0; r <= max_rank; r++) { // for(int i = 1; i <= n; i++) { // rank_count[r][i] = rank_count[r][i - 1]; // if(g[i - 1] == r) // rank_count[r][i]++; // } // } // // for(int i = 0; i <= n; i++) // for(int r = 1; r <= max_rank; r++) // rank_count[r][i] += rank_count[r - 1][i]; // // int res = find_best(n); // cout << res << endl << "Query count: " << query_count << endl; // // return 0; //}
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 4944 KB | Output is correct |
2 | Correct | 6 ms | 5000 KB | Output is correct |
3 | Correct | 7 ms | 5000 KB | Output is correct |
4 | Correct | 4 ms | 5004 KB | Output is correct |
5 | Correct | 5 ms | 5000 KB | Output is correct |
6 | Correct | 3 ms | 5004 KB | Output is correct |
7 | Correct | 5 ms | 4944 KB | Output is correct |
8 | Correct | 4 ms | 5000 KB | Output is correct |
9 | Correct | 5 ms | 5000 KB | Output is correct |
10 | Correct | 5 ms | 4944 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 5000 KB | Output is correct |
2 | Correct | 7 ms | 4984 KB | Output is correct |
3 | Correct | 4 ms | 5072 KB | Output is correct |
4 | Correct | 5 ms | 4944 KB | Output is correct |
5 | Correct | 4 ms | 5008 KB | Output is correct |
6 | Correct | 3 ms | 5008 KB | Output is correct |
7 | Correct | 5 ms | 4944 KB | Output is correct |
8 | Correct | 6 ms | 5004 KB | Output is correct |
9 | Correct | 4 ms | 4996 KB | Output is correct |
10 | Correct | 7 ms | 4944 KB | Output is correct |
11 | Correct | 9 ms | 5004 KB | Output is correct |
12 | Correct | 8 ms | 5000 KB | Output is correct |
13 | Correct | 6 ms | 5016 KB | Output is correct |
14 | Correct | 10 ms | 5016 KB | Output is correct |
15 | Correct | 45 ms | 5084 KB | Output is correct |
16 | Partially correct | 33 ms | 5116 KB | Partially correct - number of queries: 5029 |
17 | Correct | 6 ms | 5004 KB | Output is correct |
18 | Partially correct | 20 ms | 5216 KB | Partially correct - number of queries: 5038 |
19 | Correct | 6 ms | 5004 KB | Output is correct |
20 | Correct | 31 ms | 5020 KB | Output is correct |
21 | Correct | 48 ms | 5120 KB | Output is correct |
22 | Correct | 14 ms | 5092 KB | Output is correct |
23 | Correct | 7 ms | 5012 KB | Output is correct |
24 | Correct | 6 ms | 5084 KB | Output is correct |
25 | Correct | 35 ms | 5004 KB | Output is correct |
26 | Partially correct | 46 ms | 5324 KB | Partially correct - number of queries: 5091 |
27 | Correct | 6 ms | 5016 KB | Output is correct |
28 | Partially correct | 21 ms | 5140 KB | Partially correct - number of queries: 5262 |
29 | Correct | 14 ms | 5100 KB | Output is correct |
30 | Partially correct | 47 ms | 5060 KB | Partially correct - number of queries: 5074 |
31 | Correct | 5 ms | 4944 KB | Output is correct |
32 | Correct | 9 ms | 5016 KB | Output is correct |
33 | Correct | 2 ms | 4944 KB | Output is correct |
34 | Partially correct | 48 ms | 5132 KB | Partially correct - number of queries: 5114 |
35 | Correct | 8 ms | 5004 KB | Output is correct |
36 | Correct | 15 ms | 5092 KB | Output is correct |
37 | Correct | 9 ms | 4944 KB | Output is correct |
38 | Correct | 7 ms | 4944 KB | Output is correct |
39 | Partially correct | 25 ms | 5164 KB | Partially correct - number of queries: 5281 |
40 | Correct | 29 ms | 5084 KB | Output is correct |
41 | Partially correct | 50 ms | 5064 KB | Partially correct - number of queries: 5375 |
42 | Partially correct | 41 ms | 5116 KB | Partially correct - number of queries: 5375 |
43 | Partially correct | 28 ms | 5064 KB | Partially correct - number of queries: 5217 |
44 | Correct | 57 ms | 5120 KB | Output is correct |
45 | Correct | 42 ms | 5028 KB | Output is correct |
46 | Correct | 5 ms | 5004 KB | Output is correct |
47 | Correct | 31 ms | 5000 KB | Output is correct |
48 | Partially correct | 32 ms | 5124 KB | Partially correct - number of queries: 5425 |
49 | Correct | 42 ms | 5000 KB | Output is correct |
50 | Correct | 18 ms | 5136 KB | Output is correct |
51 | Correct | 40 ms | 5056 KB | Output is correct |
52 | Correct | 39 ms | 5104 KB | Output is correct |
53 | Correct | 9 ms | 5004 KB | Output is correct |
54 | Correct | 36 ms | 5032 KB | Output is correct |
55 | Correct | 7 ms | 5008 KB | Output is correct |
56 | Partially correct | 50 ms | 5148 KB | Partially correct - number of queries: 5590 |
57 | Correct | 20 ms | 5120 KB | Output is correct |
58 | Execution timed out | 3066 ms | 5128 KB | Time limit exceeded |
59 | Halted | 0 ms | 0 KB | - |