oj.uz

Submission #1112988

# Submission time Handle Problem Language Result Execution time Memory
1112988 2024-11-15T10:59:43 Z SalihSahin The Big Prize (IOI17_prize) C++14
20 / 100
 187 ms 14176 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 >= 10){
      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 28 ms 13812 KB Output is correct
2 Correct 27 ms 14080 KB Output is correct
3 Correct 29 ms 13740 KB Output is correct
4 Correct 21 ms 13188 KB Output is correct
5 Correct 28 ms 13996 KB Output is correct
6 Correct 26 ms 13816 KB Output is correct
7 Correct 27 ms 13812 KB Output is correct
8 Correct 33 ms 13740 KB Output is correct
9 Correct 27 ms 13748 KB Output is correct
10 Correct 28 ms 13824 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 13816 KB Output is correct
2 Correct 28 ms 13748 KB Output is correct
3 Correct 27 ms 13748 KB Output is correct
4 Correct 26 ms 13336 KB Output is correct
5 Correct 29 ms 13880 KB Output is correct
6 Correct 27 ms 13748 KB Output is correct
7 Correct 26 ms 13748 KB Output is correct
8 Correct 31 ms 13956 KB Output is correct
9 Correct 26 ms 13748 KB Output is correct
10 Correct 32 ms 13996 KB Output is correct
11 Correct 43 ms 13740 KB Output is correct
12 Correct 46 ms 13996 KB Output is correct
13 Correct 48 ms 13824 KB Output is correct
14 Correct 33 ms 12368 KB Output is correct
15 Partially correct 140 ms 13824 KB Partially correct - number of queries: 5654
16 Partially correct 147 ms 13824 KB Partially correct - number of queries: 5920
17 Partially correct 131 ms 13740 KB Partially correct - number of queries: 5889
18 Partially correct 145 ms 14004 KB Partially correct - number of queries: 6001
19 Partially correct 137 ms 13996 KB Partially correct - number of queries: 5643
20 Correct 75 ms 12920 KB Output is correct
21 Partially correct 150 ms 14004 KB Partially correct - number of queries: 5862
22 Correct 127 ms 13812 KB Output is correct
23 Correct 39 ms 13848 KB Output is correct
24 Correct 40 ms 13996 KB Output is correct
25 Partially correct 130 ms 13748 KB Partially correct - number of queries: 5447
26 Partially correct 138 ms 13748 KB Partially correct - number of queries: 5393
27 Correct 33 ms 13820 KB Output is correct
28 Partially correct 111 ms 13748 KB Partially correct - number of queries: 5386
29 Correct 107 ms 13748 KB Output is correct
30 Partially correct 132 ms 13748 KB Partially correct - number of queries: 5859
31 Partially correct 128 ms 13996 KB Partially correct - number of queries: 5886
32 Correct 44 ms 13816 KB Output is correct
33 Correct 11 ms 12104 KB Output is correct
34 Partially correct 132 ms 13812 KB Partially correct - number of queries: 5932
35 Correct 38 ms 13748 KB Output is correct
36 Partially correct 143 ms 13740 KB Partially correct - number of queries: 5839
37 Correct 46 ms 13748 KB Output is correct
38 Correct 34 ms 13748 KB Output is correct
39 Partially correct 145 ms 13812 KB Partially correct - number of queries: 5905
40 Partially correct 118 ms 14004 KB Partially correct - number of queries: 5201
41 Partially correct 141 ms 13844 KB Partially correct - number of queries: 5968
42 Partially correct 152 ms 13740 KB Partially correct - number of queries: 5968
43 Partially correct 139 ms 14004 KB Partially correct - number of queries: 5765
44 Partially correct 139 ms 13740 KB Partially correct - number of queries: 5871
45 Partially correct 138 ms 13748 KB Partially correct - number of queries: 5390
46 Partially correct 141 ms 13748 KB Partially correct - number of queries: 5949
47 Partially correct 136 ms 13852 KB Partially correct - number of queries: 5511
48 Partially correct 144 ms 13748 KB Partially correct - number of queries: 5965
49 Partially correct 139 ms 14004 KB Partially correct - number of queries: 5968
50 Partially correct 141 ms 13996 KB Partially correct - number of queries: 5875
51 Partially correct 137 ms 13740 KB Partially correct - number of queries: 5938
52 Partially correct 139 ms 13740 KB Partially correct - number of queries: 5929
53 Correct 34 ms 13816 KB Output is correct
54 Partially correct 132 ms 13816 KB Partially correct - number of queries: 5874
55 Partially correct 121 ms 14040 KB Partially correct - number of queries: 5882
56 Partially correct 121 ms 13328 KB Partially correct - number of queries: 5923
57 Partially correct 142 ms 13748 KB Partially correct - number of queries: 5877
58 Partially correct 140 ms 13748 KB Partially correct - number of queries: 5907
59 Partially correct 148 ms 13320 KB Partially correct - number of queries: 5868
60 Partially correct 134 ms 13256 KB Partially correct - number of queries: 5855
61 Correct 33 ms 13332 KB Output is correct
62 Correct 31 ms 13256 KB Output is correct
63 Correct 30 ms 13512 KB Output is correct
64 Correct 35 ms 13256 KB Output is correct
65 Correct 29 ms 13740 KB Output is correct
66 Correct 27 ms 13256 KB Output is correct
67 Correct 27 ms 13512 KB Output is correct
68 Correct 26 ms 13820 KB Output is correct
69 Correct 29 ms 13256 KB Output is correct
70 Correct 22 ms 13256 KB Output is correct
71 Partially correct 162 ms 14004 KB Partially correct - number of queries: 6810
72 Correct 44 ms 13740 KB Output is correct
73 Partially correct 153 ms 13740 KB Partially correct - number of queries: 6618
74 Partially correct 139 ms 13824 KB Partially correct - number of queries: 6677
75 Correct 34 ms 13840 KB Output is correct
76 Partially correct 143 ms 13748 KB Partially correct - number of queries: 5899
77 Partially correct 155 ms 13740 KB Partially correct - number of queries: 6733
78 Correct 47 ms 13824 KB Output is correct
79 Correct 87 ms 13816 KB Output is correct
80 Partially correct 173 ms 14004 KB Partially correct - number of queries: 6651
81 Partially correct 170 ms 13744 KB Partially correct - number of queries: 6732
82 Partially correct 175 ms 13996 KB Partially correct - number of queries: 6613
83 Correct 35 ms 13748 KB Output is correct
84 Partially correct 138 ms 13996 KB Partially correct - number of queries: 5616
85 Partially correct 159 ms 14176 KB Partially correct - number of queries: 6670
86 Incorrect 187 ms 13848 KB Incorrect
87 Halted 0 ms 0 KB -