oj.uz

Submission #1112984

# Submission time Handle Problem Language Result Execution time Memory
1112984 2024-11-15T10:52:39 Z SalihSahin The Big Prize (IOI17_prize) C++14
20 / 100
 211 ms 12972 KB 
#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;

   int k = rand() % 23;
   if(k >= 21){
      vector<int> delts;
      for(int i = l; i <= r; i++){
         delts.pb(i);
      } 
      random_shuffle(delts.begin(), delts.end());
      for(int i = 0; i < delts.size(); i++){
         if(check[delts[i]][0] == -1) check[delts[i]] = ask(delts[i]);
         if(check[delts[i]][0] + check[delts[i]][1] == smallcnt){
            m = delts[i];
            break;
         }
         else{
            small[delts[i]] = 1;
         }
      }
   }
   else{
      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 = kokbul(n) + 15;
   kok = min(kok, 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;
         }
      }
   }
   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;
}*/

Compilation message

prize.cpp: In function 'void f(int, int, int, int, int)':
prize.cpp:52:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |       for(int i = 0; i < delts.size(); i++){
      |                      ~~^~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 12112 KB Output is correct
2 Correct 15 ms 12112 KB Output is correct
3 Correct 19 ms 12172 KB Output is correct
4 Correct 19 ms 12112 KB Output is correct
5 Correct 19 ms 12184 KB Output is correct
6 Correct 17 ms 12368 KB Output is correct
7 Correct 19 ms 12188 KB Output is correct
8 Correct 19 ms 12112 KB Output is correct
9 Correct 21 ms 12112 KB Output is correct
10 Correct 17 ms 12112 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 12112 KB Output is correct
2 Correct 20 ms 12368 KB Output is correct
3 Correct 20 ms 12112 KB Output is correct
4 Correct 17 ms 12112 KB Output is correct
5 Correct 20 ms 12112 KB Output is correct
6 Correct 21 ms 12112 KB Output is correct
7 Correct 22 ms 12112 KB Output is correct
8 Correct 19 ms 12112 KB Output is correct
9 Correct 20 ms 12112 KB Output is correct
10 Correct 19 ms 12112 KB Output is correct
11 Correct 26 ms 12516 KB Output is correct
12 Correct 27 ms 12428 KB Output is correct
13 Correct 31 ms 12616 KB Output is correct
14 Correct 25 ms 12184 KB Output is correct
15 Partially correct 110 ms 12700 KB Partially correct - number of queries: 5084
16 Partially correct 116 ms 12176 KB Partially correct - number of queries: 5326
17 Partially correct 107 ms 12420 KB Partially correct - number of queries: 5322
18 Partially correct 94 ms 12740 KB Partially correct - number of queries: 5297
19 Partially correct 107 ms 12364 KB Partially correct - number of queries: 5028
20 Correct 66 ms 12180 KB Output is correct
21 Partially correct 105 ms 12432 KB Partially correct - number of queries: 5262
22 Correct 72 ms 12444 KB Output is correct
23 Correct 17 ms 12180 KB Output is correct
24 Correct 22 ms 12360 KB Output is correct
25 Correct 85 ms 12720 KB Output is correct
26 Correct 90 ms 12740 KB Output is correct
27 Correct 22 ms 12172 KB Output is correct
28 Correct 96 ms 12204 KB Output is correct
29 Correct 79 ms 12360 KB Output is correct
30 Partially correct 110 ms 12124 KB Partially correct - number of queries: 5262
31 Partially correct 115 ms 12368 KB Partially correct - number of queries: 5264
32 Correct 24 ms 12440 KB Output is correct
33 Correct 11 ms 12280 KB Output is correct
34 Partially correct 108 ms 12360 KB Partially correct - number of queries: 5310
35 Correct 26 ms 12368 KB Output is correct
36 Partially correct 110 ms 12364 KB Partially correct - number of queries: 5273
37 Correct 24 ms 12368 KB Output is correct
38 Correct 22 ms 12368 KB Output is correct
39 Partially correct 107 ms 12360 KB Partially correct - number of queries: 5262
40 Correct 85 ms 12728 KB Output is correct
41 Partially correct 108 ms 12112 KB Partially correct - number of queries: 5340
42 Partially correct 107 ms 12196 KB Partially correct - number of queries: 5340
43 Partially correct 108 ms 12460 KB Partially correct - number of queries: 5181
44 Partially correct 105 ms 12112 KB Partially correct - number of queries: 5316
45 Correct 86 ms 12112 KB Output is correct
46 Partially correct 92 ms 12612 KB Partially correct - number of queries: 5308
47 Correct 93 ms 12368 KB Output is correct
48 Partially correct 113 ms 12828 KB Partially correct - number of queries: 5318
49 Partially correct 110 ms 12288 KB Partially correct - number of queries: 5320
50 Partially correct 112 ms 12264 KB Partially correct - number of queries: 5311
51 Partially correct 100 ms 12112 KB Partially correct - number of queries: 5303
52 Partially correct 108 ms 12436 KB Partially correct - number of queries: 5324
53 Correct 25 ms 12184 KB Output is correct
54 Partially correct 99 ms 12292 KB Partially correct - number of queries: 5261
55 Partially correct 90 ms 12620 KB Partially correct - number of queries: 5345
56 Partially correct 105 ms 12192 KB Partially correct - number of queries: 5313
57 Partially correct 107 ms 12360 KB Partially correct - number of queries: 5276
58 Partially correct 105 ms 12336 KB Partially correct - number of queries: 5313
59 Partially correct 109 ms 12444 KB Partially correct - number of queries: 5347
60 Partially correct 122 ms 12208 KB Partially correct - number of queries: 5279
61 Correct 21 ms 12596 KB Output is correct
62 Correct 20 ms 12360 KB Output is correct
63 Correct 20 ms 12368 KB Output is correct
64 Correct 20 ms 12360 KB Output is correct
65 Correct 19 ms 12112 KB Output is correct
66 Correct 24 ms 12112 KB Output is correct
67 Correct 24 ms 12368 KB Output is correct
68 Correct 17 ms 12112 KB Output is correct
69 Correct 25 ms 12172 KB Output is correct
70 Correct 21 ms 12112 KB Output is correct
71 Partially correct 90 ms 12616 KB Partially correct - number of queries: 5421
72 Correct 27 ms 12332 KB Output is correct
73 Partially correct 105 ms 12360 KB Partially correct - number of queries: 5379
74 Partially correct 112 ms 12556 KB Partially correct - number of queries: 5386
75 Correct 23 ms 12336 KB Output is correct
76 Correct 94 ms 12972 KB Output is correct
77 Partially correct 113 ms 12464 KB Partially correct - number of queries: 5497
78 Correct 30 ms 12240 KB Output is correct
79 Correct 63 ms 12180 KB Output is correct
80 Partially correct 124 ms 12616 KB Partially correct - number of queries: 5493
81 Partially correct 118 ms 12616 KB Partially correct - number of queries: 5490
82 Partially correct 113 ms 12440 KB Partially correct - number of queries: 5405
83 Correct 17 ms 12368 KB Output is correct
84 Correct 88 ms 12548 KB Output is correct
85 Partially correct 124 ms 12364 KB Partially correct - number of queries: 5451
86 Incorrect 211 ms 12180 KB Incorrect
87 Halted 0 ms 0 KB -