oj.uz

Submission #797018

# Submission time Handle Problem Language Result Execution time Memory
797018 2023-07-29T04:38:31 Z cig32 Mađioničar (COI22_madionicar) C++17
38 / 100
 1562 ms 1560 KB 
#include "bits/stdc++.h"
using namespace std;
#define int long long
const int MAXN = 3e5 + 10;
const int MOD = 1e9 + 7;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int bm(int b, int p) {
  if(p==0) return 1 % MOD;
  int r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
int inv(int b) { 
  return bm(b, MOD-2);
}
int fastlog(int x) {
  return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
void printcase(int i) { cout << "Case #" << i << ": "; }
int qc=0;
string s;
int isp(int l, int r) {
  qc++;
  cout << "? " << l << ' ' << r << endl;
  int x; cin >> x; return x;
}
void solve(int tc) {
  int n;
  cin >> n;
  int s[n+1];
  int nw = 2;
  deque<int>dq;
  int ans=0;
  for(int i=1;i<=n;i++){
    while(dq.size()) {
      int l = dq.back() / 2, r = (dq.back() + 1) / 2;
      l -= (i - r);
      r = i;
      if(l >= 1 && isp(l, r)) {
        break;
      }
      else {
        dq.pop_back();
      }
    }
    if(i == 1) s[i] = 1;
    else if(dq.size()) {
      int l = dq.back() / 2, r = (dq.back() + 1) / 2;
      l -= (i - r);
      r = i;
      s[i] = s[l];
      if(s[i] == s[i-1]) {
        dq.push_front(2*i-1);
      }
    }
    else {
      if(isp(i-1, i)) {
        dq.push_front(2*i-1);
        s[i] = s[i-1];
      }
      else {
        s[i] = nw++;
      }
    }
    dq.push_front(2*i);
    int l = dq.back() / 2, r = (dq.back() + 1) / 2;
    l -= (i - r);
    r = i;
    ans = max(ans, r-l+1);
  }
  cout << "! " << ans << endl;
  //cerr << "Nr of queries = " << qc << endl;
}
int32_t main() {
  //ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}
// 勿忘初衷

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 336 KB Output is correct
2 Correct 121 ms 336 KB Output is correct
3 Correct 75 ms 452 KB Output is correct
4 Correct 151 ms 336 KB Output is correct
5 Correct 118 ms 336 KB Output is correct
6 Correct 124 ms 336 KB Output is correct
7 Correct 79 ms 336 KB Output is correct
8 Correct 119 ms 360 KB Output is correct
9 Correct 135 ms 336 KB Output is correct
10 Correct 132 ms 336 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 336 KB Output is correct
2 Correct 121 ms 336 KB Output is correct
3 Correct 75 ms 452 KB Output is correct
4 Correct 151 ms 336 KB Output is correct
5 Correct 118 ms 336 KB Output is correct
6 Correct 124 ms 336 KB Output is correct
7 Correct 79 ms 336 KB Output is correct
8 Correct 119 ms 360 KB Output is correct
9 Correct 135 ms 336 KB Output is correct
10 Correct 132 ms 336 KB Output is correct
11 Correct 1096 ms 720 KB Output is correct
12 Correct 949 ms 720 KB Output is correct
13 Correct 945 ms 720 KB Output is correct
14 Correct 1342 ms 944 KB Output is correct
15 Correct 1034 ms 828 KB Output is correct
16 Correct 1562 ms 1444 KB Output is correct
17 Correct 870 ms 1392 KB Output is correct
18 Correct 737 ms 720 KB Output is correct
19 Correct 1129 ms 1560 KB Output is correct
20 Correct 827 ms 680 KB Output is correct
21 Correct 795 ms 720 KB Output is correct
22 Correct 862 ms 792 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1453 ms 1068 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 336 KB Output is correct
2 Correct 121 ms 336 KB Output is correct
3 Correct 75 ms 452 KB Output is correct
4 Correct 151 ms 336 KB Output is correct
5 Correct 118 ms 336 KB Output is correct
6 Correct 124 ms 336 KB Output is correct
7 Correct 79 ms 336 KB Output is correct
8 Correct 119 ms 360 KB Output is correct
9 Correct 135 ms 336 KB Output is correct
10 Correct 132 ms 336 KB Output is correct
11 Correct 1096 ms 720 KB Output is correct
12 Correct 949 ms 720 KB Output is correct
13 Correct 945 ms 720 KB Output is correct
14 Correct 1342 ms 944 KB Output is correct
15 Correct 1034 ms 828 KB Output is correct
16 Correct 1562 ms 1444 KB Output is correct
17 Correct 870 ms 1392 KB Output is correct
18 Correct 737 ms 720 KB Output is correct
19 Correct 1129 ms 1560 KB Output is correct
20 Correct 827 ms 680 KB Output is correct
21 Correct 795 ms 720 KB Output is correct
22 Correct 862 ms 792 KB Output is correct
23 Runtime error 1453 ms 1068 KB Execution killed with signal 13
24 Halted 0 ms 0 KB -