Submission #1112993

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1112993	2024-11-15T11:04:04 Z	SalihSahin	The Big Prize (IOI17_prize)	C++14	95.18 / 100	121 ms	12368 KB

prize

#include <bits/stdc++.h>
#define pb push_back
#include "prize.h"

using namespace std;
/*
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;
      //cout<<query_count<<" babag "<<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;
}
*/

const int MAXN = 2e5 + 5;
vector<vector<int> > check(MAXN, vector<int>(2, -1));
vector<int> small(MAXN);

void f(int n, int smallcnt, int l, int r, int cnt){
   if(l == r){
      small[l] = 1;
      return;
   }
   int mid = (l + r)/2;
   int m = -1;

   for(int delt = 0; delt <= (r - l + 1)/2 + 1; delt++){
      if(mid + delt <= r){
         if(check[mid + delt][0] == -1) check[mid + delt] = ask(mid + delt);
         if(check[mid + delt][0] + check[mid + delt][1] == smallcnt){
            m = mid + delt;
            break;
         }
         else{
            small[mid + delt] = 1;
         }
      }

      if(mid - delt >= l){
         if(check[mid - delt][0] == -1) check[mid - delt] = ask(mid - delt);
         if(check[mid - delt][0] + check[mid - delt][1] == smallcnt){
            m = mid - delt;
            break;
         }
         else{
            small[mid - delt] = 1;
         }
      }
   }

   if(m == -1) return; // aralıktaki herkes small ve tagledik
   if(l > 0 && check[l-1][0] == -1) check[l-1] = ask(l-1);
   if(r < n-1 && check[r+1][0] == -1) check[r+1] = ask(r+1);

   int solcnt = check[m][0] - (l > 0 ? check[l-1][0] : 0);
   int sagcnt = check[m][1] - (r < n-1 ? check[r+1][1] : 0);
   if(l <= m-1 && solcnt > 0){
      //cout<<l<<" - "<<m-1<<" -> "<<solcnt<<endl;
      f(n, smallcnt, l, m-1, solcnt);
   }

   if(m+1 <= r && sagcnt > 0){
      //cout<<m+1<<" - "<<r<<" -> "<<sagcnt<<endl;
      f(n, smallcnt, m+1, r, sagcnt);
   }
}

long long kokbul(long long n){
   long long l = 1, r = n;
   while(l < r){
      long long m = (l + r)/2;

      if(m * m < n) l = m + 1;
      else r = m;
   }

   return l;
}

int find_best(int n) {
   int smallcnt = 0;
   int kok = min(600, n);

   for(int i = 0; i < kok; i++){
      check[i] = ask(i);
      smallcnt = max(smallcnt, check[i][0] + check[i][1]);
   }
   for(int i = 0; i < kok; i++){
      if(check[i][0] + check[i][1] < smallcnt) small[i] = 1;
   }

   f(n, smallcnt, 0, n-1, smallcnt);
   int ans = -1;
   for(int i = 0; i < n; i++){
      if(small[i] == 1){
         if(check[i][0] == -1) check[i] = ask(i);
         if(check[i][0] + check[i][1] == 0){
            ans = i;
            break;
         }
      }
   }
   return ans;
}
/*
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;
}
*/
/*
int main() {
   mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
   int mx = 0;
   int t;
   cin>>t;
   while(t--){
      //cin>>n;
      //n = rng() % 55 + 7;
      n = 2e5 - rng() % 5000;
      g.resize(n);

      vector<int> cnts(3);
      cnts[0] = 1;
      cnts[1] = 3;
      cnts[2] = rng()%10 + 10;
      cnts[3] = rng()%20 + 400;
      cnts[4] = n - cnts[3] - cnts[2] - cnts[1] - cnts[0];

      for(int i = 0; i < n; i++){
         small[i] = 0;
         check[i][0] = check[i][1] = -1;
      }
      int ind = 0;
      for(int i = 0; i < n; i++){
         if(cnts[ind] == 0) ind++;
         g[i] = ind + 1;
         cnts[ind]--;
      }

      shuffle(g.begin(), g.end(), rng);

      for(int i = 0; i < n; 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.clear();
      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);
      if(res == -1 || query_count > max_q){
         cout << res << endl << "Query count: " << query_count << endl;
      }
      mx = max(mx, query_count);
      query_count = 0;
   }
   cout<<mx<<endl;
   return 0;
}*/

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	12112 KB	Output is correct
2	Correct	20 ms	12368 KB	Output is correct
3	Correct	21 ms	12284 KB	Output is correct
4	Correct	27 ms	12192 KB	Output is correct
5	Correct	20 ms	12112 KB	Output is correct
6	Correct	19 ms	12180 KB	Output is correct
7	Correct	19 ms	12112 KB	Output is correct
8	Correct	19 ms	12112 KB	Output is correct
9	Correct	21 ms	12180 KB	Output is correct
10	Correct	25 ms	12112 KB	Output is correct

Subtask #2

75.18 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	12264 KB	Output is correct
2	Correct	20 ms	12112 KB	Output is correct
3	Correct	18 ms	12112 KB	Output is correct
4	Correct	18 ms	12112 KB	Output is correct
5	Correct	21 ms	12112 KB	Output is correct
6	Correct	19 ms	12112 KB	Output is correct
7	Correct	22 ms	12112 KB	Output is correct
8	Correct	21 ms	12368 KB	Output is correct
9	Correct	21 ms	12284 KB	Output is correct
10	Correct	20 ms	12112 KB	Output is correct
11	Correct	25 ms	12064 KB	Output is correct
12	Correct	25 ms	12112 KB	Output is correct
13	Correct	30 ms	11968 KB	Output is correct
14	Correct	36 ms	12112 KB	Output is correct
15	Correct	105 ms	12112 KB	Output is correct
16	Partially correct	109 ms	12112 KB	Partially correct - number of queries: 5326
17	Partially correct	87 ms	12280 KB	Partially correct - number of queries: 5205
18	Partially correct	108 ms	12176 KB	Partially correct - number of queries: 5354
19	Correct	96 ms	12172 KB	Output is correct
20	Correct	79 ms	12172 KB	Output is correct
21	Partially correct	98 ms	12112 KB	Partially correct - number of queries: 5225
22	Correct	84 ms	12112 KB	Output is correct
23	Correct	25 ms	12112 KB	Output is correct
24	Correct	27 ms	12112 KB	Output is correct
25	Correct	94 ms	12184 KB	Output is correct
26	Correct	96 ms	12112 KB	Output is correct
27	Correct	23 ms	12112 KB	Output is correct
28	Correct	107 ms	12112 KB	Output is correct
29	Correct	90 ms	12112 KB	Output is correct
30	Partially correct	109 ms	12112 KB	Partially correct - number of queries: 5323
31	Partially correct	109 ms	12112 KB	Partially correct - number of queries: 5155
32	Correct	27 ms	12180 KB	Output is correct
33	Correct	12 ms	12112 KB	Output is correct
34	Partially correct	100 ms	12004 KB	Partially correct - number of queries: 5239
35	Correct	22 ms	12112 KB	Output is correct
36	Partially correct	108 ms	12112 KB	Partially correct - number of queries: 5200
37	Correct	25 ms	12112 KB	Output is correct
38	Correct	22 ms	12112 KB	Output is correct
39	Partially correct	101 ms	12280 KB	Partially correct - number of queries: 5238
40	Correct	92 ms	12112 KB	Output is correct
41	Partially correct	101 ms	12112 KB	Partially correct - number of queries: 5290
42	Partially correct	121 ms	12112 KB	Partially correct - number of queries: 5290
43	Partially correct	103 ms	12112 KB	Partially correct - number of queries: 5148
44	Partially correct	103 ms	12112 KB	Partially correct - number of queries: 5254
45	Correct	92 ms	12172 KB	Output is correct
46	Partially correct	112 ms	12280 KB	Partially correct - number of queries: 5201
47	Correct	97 ms	12112 KB	Output is correct
48	Partially correct	119 ms	12360 KB	Partially correct - number of queries: 5303
49	Partially correct	99 ms	12176 KB	Partially correct - number of queries: 5221
50	Partially correct	116 ms	12176 KB	Partially correct - number of queries: 5359
51	Partially correct	97 ms	12188 KB	Partially correct - number of queries: 5252
52	Partially correct	97 ms	12112 KB	Partially correct - number of queries: 5192
53	Correct	20 ms	12112 KB	Output is correct
54	Partially correct	101 ms	12364 KB	Partially correct - number of queries: 5233
55	Partially correct	110 ms	12112 KB	Partially correct - number of queries: 5189
56	Partially correct	93 ms	12184 KB	Partially correct - number of queries: 5358
57	Partially correct	106 ms	12112 KB	Partially correct - number of queries: 5274
58	Partially correct	95 ms	12112 KB	Partially correct - number of queries: 5314
59	Partially correct	118 ms	12112 KB	Partially correct - number of queries: 5296
60	Partially correct	108 ms	12112 KB	Partially correct - number of queries: 5235
61	Correct	22 ms	12184 KB	Output is correct
62	Correct	22 ms	12112 KB	Output is correct
63	Correct	19 ms	12112 KB	Output is correct
64	Correct	26 ms	12112 KB	Output is correct
65	Correct	23 ms	12112 KB	Output is correct
66	Correct	31 ms	12112 KB	Output is correct
67	Correct	29 ms	12112 KB	Output is correct
68	Correct	23 ms	12112 KB	Output is correct
69	Correct	27 ms	12112 KB	Output is correct
70	Correct	23 ms	12112 KB	Output is correct
71	Partially correct	104 ms	12180 KB	Partially correct - number of queries: 5358
72	Correct	30 ms	12176 KB	Output is correct
73	Partially correct	107 ms	12112 KB	Partially correct - number of queries: 5295
74	Partially correct	104 ms	12112 KB	Partially correct - number of queries: 5322
75	Correct	23 ms	12112 KB	Output is correct
76	Correct	101 ms	12112 KB	Output is correct
77	Partially correct	112 ms	12176 KB	Partially correct - number of queries: 5452
78	Correct	34 ms	12152 KB	Output is correct
79	Correct	57 ms	12172 KB	Output is correct
80	Partially correct	105 ms	12112 KB	Partially correct - number of queries: 5482
81	Partially correct	111 ms	12112 KB	Partially correct - number of queries: 5466
82	Partially correct	111 ms	11952 KB	Partially correct - number of queries: 5418
83	Correct	26 ms	12112 KB	Output is correct
84	Correct	84 ms	12112 KB	Output is correct
85	Partially correct	118 ms	12176 KB	Partially correct - number of queries: 5449
86	Correct	19 ms	12144 KB	Output is correct
87	Correct	27 ms	12112 KB	Output is correct
88	Correct	22 ms	12364 KB	Output is correct
89	Correct	23 ms	12112 KB	Output is correct
90	Correct	25 ms	12124 KB	Output is correct
91	Correct	20 ms	12112 KB	Output is correct
92	Correct	29 ms	12124 KB	Output is correct
93	Correct	23 ms	12112 KB	Output is correct
94	Correct	25 ms	12032 KB	Output is correct
95	Correct	26 ms	12280 KB	Output is correct
96	Correct	23 ms	12112 KB	Output is correct
97	Correct	18 ms	12112 KB	Output is correct