oj.uz

Submission #1112987

# Submission time Handle Problem Language Result Execution time Memory
1112987 2024-11-15T10:58:47 Z SalihSahin The Big Prize (IOI17_prize) C++14
20 / 100
 198 ms 12940 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 >= 18){
      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 15 ms 12112 KB Output is correct
2 Correct 15 ms 12176 KB Output is correct
3 Correct 17 ms 12112 KB Output is correct
4 Correct 17 ms 12184 KB Output is correct
5 Correct 18 ms 12112 KB Output is correct
6 Correct 18 ms 12112 KB Output is correct
7 Correct 17 ms 12112 KB Output is correct
8 Correct 17 ms 12176 KB Output is correct
9 Correct 16 ms 12112 KB Output is correct
10 Correct 18 ms 12112 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 12360 KB Output is correct
2 Correct 19 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 17 ms 12112 KB Output is correct
6 Correct 17 ms 12112 KB Output is correct
7 Correct 24 ms 12112 KB Output is correct
8 Correct 20 ms 12120 KB Output is correct
9 Correct 18 ms 12188 KB Output is correct
10 Correct 19 ms 12112 KB Output is correct
11 Correct 28 ms 12544 KB Output is correct
12 Correct 29 ms 12572 KB Output is correct
13 Correct 30 ms 12544 KB Output is correct
14 Correct 29 ms 12112 KB Output is correct
15 Partially correct 113 ms 12492 KB Partially correct - number of queries: 5223
16 Partially correct 105 ms 12592 KB Partially correct - number of queries: 5447
17 Partially correct 114 ms 12584 KB Partially correct - number of queries: 5448
18 Partially correct 104 ms 12112 KB Partially correct - number of queries: 5488
19 Partially correct 94 ms 12784 KB Partially correct - number of queries: 5158
20 Correct 81 ms 12072 KB Output is correct
21 Partially correct 87 ms 12412 KB Partially correct - number of queries: 5468
22 Correct 75 ms 12616 KB Output is correct
23 Correct 28 ms 12460 KB Output is correct
24 Correct 25 ms 12524 KB Output is correct
25 Partially correct 96 ms 12772 KB Partially correct - number of queries: 5074
26 Partially correct 95 ms 12716 KB Partially correct - number of queries: 5020
27 Correct 18 ms 12748 KB Output is correct
28 Partially correct 93 ms 12428 KB Partially correct - number of queries: 5042
29 Correct 81 ms 12920 KB Output is correct
30 Partially correct 103 ms 12428 KB Partially correct - number of queries: 5442
31 Partially correct 92 ms 12748 KB Partially correct - number of queries: 5427
32 Correct 28 ms 12360 KB Output is correct
33 Correct 11 ms 12112 KB Output is correct
34 Partially correct 108 ms 12368 KB Partially correct - number of queries: 5452
35 Correct 26 ms 12524 KB Output is correct
36 Partially correct 96 ms 12304 KB Partially correct - number of queries: 5413
37 Correct 28 ms 12620 KB Output is correct
38 Correct 21 ms 12368 KB Output is correct
39 Partially correct 88 ms 12468 KB Partially correct - number of queries: 5454
40 Correct 97 ms 12516 KB Output is correct
41 Partially correct 103 ms 12640 KB Partially correct - number of queries: 5483
42 Partially correct 108 ms 12812 KB Partially correct - number of queries: 5483
43 Partially correct 110 ms 12360 KB Partially correct - number of queries: 5335
44 Partially correct 110 ms 12500 KB Partially correct - number of queries: 5449
45 Partially correct 99 ms 12360 KB Partially correct - number of queries: 5058
46 Partially correct 104 ms 12784 KB Partially correct - number of queries: 5490
47 Partially correct 106 ms 12580 KB Partially correct - number of queries: 5074
48 Partially correct 97 ms 12644 KB Partially correct - number of queries: 5475
49 Partially correct 118 ms 12488 KB Partially correct - number of queries: 5449
50 Partially correct 111 ms 12672 KB Partially correct - number of queries: 5485
51 Partially correct 97 ms 12436 KB Partially correct - number of queries: 5455
52 Partially correct 107 ms 12888 KB Partially correct - number of queries: 5485
53 Correct 23 ms 12696 KB Output is correct
54 Partially correct 107 ms 12244 KB Partially correct - number of queries: 5422
55 Partially correct 106 ms 12872 KB Partially correct - number of queries: 5474
56 Partially correct 101 ms 12416 KB Partially correct - number of queries: 5474
57 Partially correct 100 ms 12688 KB Partially correct - number of queries: 5438
58 Partially correct 93 ms 12704 KB Partially correct - number of queries: 5438
59 Partially correct 109 ms 12876 KB Partially correct - number of queries: 5496
60 Partially correct 96 ms 12488 KB Partially correct - number of queries: 5448
61 Correct 20 ms 12360 KB Output is correct
62 Correct 21 ms 12368 KB Output is correct
63 Correct 25 ms 12192 KB Output is correct
64 Correct 20 ms 12728 KB Output is correct
65 Correct 16 ms 12124 KB Output is correct
66 Correct 26 ms 12112 KB Output is correct
67 Correct 25 ms 12184 KB Output is correct
68 Correct 17 ms 12112 KB Output is correct
69 Correct 28 ms 12112 KB Output is correct
70 Correct 22 ms 12112 KB Output is correct
71 Partially correct 125 ms 12608 KB Partially correct - number of queries: 5733
72 Correct 27 ms 12520 KB Output is correct
73 Partially correct 99 ms 12304 KB Partially correct - number of queries: 5661
74 Partially correct 104 ms 12556 KB Partially correct - number of queries: 5674
75 Correct 19 ms 12176 KB Output is correct
76 Partially correct 99 ms 12576 KB Partially correct - number of queries: 5050
77 Partially correct 111 ms 12360 KB Partially correct - number of queries: 5724
78 Correct 26 ms 12824 KB Output is correct
79 Correct 70 ms 12512 KB Output is correct
80 Partially correct 121 ms 12332 KB Partially correct - number of queries: 5766
81 Partially correct 103 ms 12900 KB Partially correct - number of queries: 5738
82 Partially correct 129 ms 12940 KB Partially correct - number of queries: 5681
83 Correct 23 ms 12548 KB Output is correct
84 Correct 96 ms 12344 KB Output is correct
85 Partially correct 123 ms 12436 KB Partially correct - number of queries: 5728
86 Incorrect 198 ms 12112 KB Incorrect
87 Halted 0 ms 0 KB -