oj.uz

Submission #516391

# Submission time Handle Problem Language Result Execution time Memory
516391 2022-01-21T09:09:00 Z Wayne_Yan Colors (BOI20_colors) C++17
0 / 100
 1 ms 284 KB 
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#define int long long
typedef int64_t ll;
typedef long double ld;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pb emplace_back
#define mp make_pair
#define mt make_tuple
#define pii pair<int,int>
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define RF(n) RFi(i,n)
#define RFi(i,n) RFl(i,0,n)
#define RFl(i,l,n) for(int i=n-1;i>=l;i--)
#define all(v) begin(v),end(v)
#define siz(v) (ll(v.size()))
#define get_pos(v,x) (lower_bound(all(v),x)-begin(v))
#define sort_uni(v) sort(begin(v),end(v)),v.erase(unique(begin(v),end(v)),end(v))
#define mem(v,x) memset(v,x,sizeof v)
#define ff first
#define ss second
#define mid ((l+r)>>1)
#define RAN(a,b) uniform_int_distribution<int> (a, b)(rng)
#define debug(x) (cerr << (#x) << " = " << x << "\n")
#define cmax(a,b) (a = max(a,b))
#define cmin(a,b) (a = min(a,b))

template <typename T> using max_heap = __gnu_pbds::priority_queue<T,less<T> >;
template <typename T> using min_heap = __gnu_pbds::priority_queue<T,greater<T> >;
template <typename T> using rbt = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

//int C;

int pre = 0;

int q(int c){
  printf("? %lld\n", c);
  cout.flush();

  /*
  bool b = (abs(pre - c) >= C);  
  pre = c;
  return b;
  */

  
  int x;
  cin >> x;
  return x;
  
}

signed main(){
  
  int N;
  cin >> N;

  int l = 0, r = N;
  int dis = 0;
  int flip = 0;
  while(l+1 != r){
    if(flip) dis -= mid;
    else dis += mid;
    l = mid;
    flip = 1 - flip;
  }

  if(dis < 0) dis = -dis;
  int pointer = dis+1;
  q(pointer);

  l = 0, r = N;

  while(l+1 != r){
    if(pointer + mid <= N){
      pointer += mid;
    }else if(pointer-mid >= 1){
      pointer -= mid;
    }else{
      assert(0);
    }

    if(q(pointer)){
      r = mid; 
    }else{
      l = mid;
    }
  }

  printf("= %lld\n", r);

  return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB OK (4 queries)
2 Correct 0 ms 200 KB OK (7 queries)
3 Correct 0 ms 200 KB OK (4 queries)
4 Correct 0 ms 200 KB OK (5 queries)
5 Correct 0 ms 200 KB OK (5 queries)
6 Correct 0 ms 284 KB OK (7 queries)
7 Correct 0 ms 200 KB OK (7 queries)
8 Correct 1 ms 200 KB OK (6 queries)
9 Correct 1 ms 200 KB OK (7 queries)
10 Correct 0 ms 200 KB OK (4 queries)
11 Correct 0 ms 200 KB OK (5 queries)
12 Correct 1 ms 200 KB OK (6 queries)
13 Correct 0 ms 200 KB OK (7 queries)
14 Correct 1 ms 284 KB OK (7 queries)
15 Correct 0 ms 200 KB OK (7 queries)
16 Correct 1 ms 200 KB OK (7 queries)
17 Correct 0 ms 200 KB OK (7 queries)
18 Correct 0 ms 200 KB OK (6 queries)
19 Correct 1 ms 200 KB OK (6 queries)
20 Correct 0 ms 200 KB OK (7 queries)
21 Correct 0 ms 200 KB OK (7 queries)
22 Correct 0 ms 200 KB OK (2 queries)
23 Correct 0 ms 200 KB OK (2 queries)
24 Correct 0 ms 200 KB OK (3 queries)
25 Correct 0 ms 200 KB OK (3 queries)
26 Correct 0 ms 200 KB OK (2 queries)
27 Correct 0 ms 200 KB OK (3 queries)
28 Correct 1 ms 200 KB OK (3 queries)
29 Correct 1 ms 200 KB OK (3 queries)
30 Correct 0 ms 200 KB OK (3 queries)
31 Correct 1 ms 200 KB OK (4 queries)
32 Correct 0 ms 200 KB OK (4 queries)
33 Correct 0 ms 200 KB OK (3 queries)
34 Correct 0 ms 200 KB OK (3 queries)
35 Correct 0 ms 200 KB OK (3 queries)
36 Correct 0 ms 200 KB OK (4 queries)
37 Correct 0 ms 200 KB OK (4 queries)
38 Correct 0 ms 200 KB OK (3 queries)
39 Incorrect 0 ms 200 KB Hair color 5 was used multiple times
40 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB OK (4 queries)
2 Correct 0 ms 200 KB OK (7 queries)
3 Correct 0 ms 200 KB OK (4 queries)
4 Correct 0 ms 200 KB OK (5 queries)
5 Correct 0 ms 200 KB OK (5 queries)
6 Correct 0 ms 284 KB OK (7 queries)
7 Correct 0 ms 200 KB OK (7 queries)
8 Correct 1 ms 200 KB OK (6 queries)
9 Correct 1 ms 200 KB OK (7 queries)
10 Correct 0 ms 200 KB OK (4 queries)
11 Correct 0 ms 200 KB OK (5 queries)
12 Correct 1 ms 200 KB OK (6 queries)
13 Correct 0 ms 200 KB OK (7 queries)
14 Correct 1 ms 284 KB OK (7 queries)
15 Correct 0 ms 200 KB OK (7 queries)
16 Correct 1 ms 200 KB OK (7 queries)
17 Correct 0 ms 200 KB OK (7 queries)
18 Correct 0 ms 200 KB OK (6 queries)
19 Correct 1 ms 200 KB OK (6 queries)
20 Correct 0 ms 200 KB OK (7 queries)
21 Correct 0 ms 200 KB OK (7 queries)
22 Correct 0 ms 200 KB OK (2 queries)
23 Correct 0 ms 200 KB OK (2 queries)
24 Correct 0 ms 200 KB OK (3 queries)
25 Correct 0 ms 200 KB OK (3 queries)
26 Correct 0 ms 200 KB OK (2 queries)
27 Correct 0 ms 200 KB OK (3 queries)
28 Correct 1 ms 200 KB OK (3 queries)
29 Correct 1 ms 200 KB OK (3 queries)
30 Correct 0 ms 200 KB OK (3 queries)
31 Correct 1 ms 200 KB OK (4 queries)
32 Correct 0 ms 200 KB OK (4 queries)
33 Correct 0 ms 200 KB OK (3 queries)
34 Correct 0 ms 200 KB OK (3 queries)
35 Correct 0 ms 200 KB OK (3 queries)
36 Correct 0 ms 200 KB OK (4 queries)
37 Correct 0 ms 200 KB OK (4 queries)
38 Correct 0 ms 200 KB OK (3 queries)
39 Incorrect 0 ms 200 KB Hair color 5 was used multiple times
40 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB OK (4 queries)
2 Correct 0 ms 200 KB OK (7 queries)
3 Correct 0 ms 200 KB OK (4 queries)
4 Correct 0 ms 200 KB OK (5 queries)
5 Correct 0 ms 200 KB OK (5 queries)
6 Correct 0 ms 284 KB OK (7 queries)
7 Correct 0 ms 200 KB OK (7 queries)
8 Correct 1 ms 200 KB OK (6 queries)
9 Correct 1 ms 200 KB OK (7 queries)
10 Correct 0 ms 200 KB OK (4 queries)
11 Correct 0 ms 200 KB OK (5 queries)
12 Correct 1 ms 200 KB OK (6 queries)
13 Correct 0 ms 200 KB OK (7 queries)
14 Correct 1 ms 284 KB OK (7 queries)
15 Correct 0 ms 200 KB OK (7 queries)
16 Correct 1 ms 200 KB OK (7 queries)
17 Correct 0 ms 200 KB OK (7 queries)
18 Correct 0 ms 200 KB OK (6 queries)
19 Correct 1 ms 200 KB OK (6 queries)
20 Correct 0 ms 200 KB OK (7 queries)
21 Correct 0 ms 200 KB OK (7 queries)
22 Correct 0 ms 200 KB OK (2 queries)
23 Correct 0 ms 200 KB OK (2 queries)
24 Correct 0 ms 200 KB OK (3 queries)
25 Correct 0 ms 200 KB OK (3 queries)
26 Correct 0 ms 200 KB OK (2 queries)
27 Correct 0 ms 200 KB OK (3 queries)
28 Correct 1 ms 200 KB OK (3 queries)
29 Correct 1 ms 200 KB OK (3 queries)
30 Correct 0 ms 200 KB OK (3 queries)
31 Correct 1 ms 200 KB OK (4 queries)
32 Correct 0 ms 200 KB OK (4 queries)
33 Correct 0 ms 200 KB OK (3 queries)
34 Correct 0 ms 200 KB OK (3 queries)
35 Correct 0 ms 200 KB OK (3 queries)
36 Correct 0 ms 200 KB OK (4 queries)
37 Correct 0 ms 200 KB OK (4 queries)
38 Correct 0 ms 200 KB OK (3 queries)
39 Incorrect 0 ms 200 KB Hair color 5 was used multiple times
40 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB OK (4 queries)
2 Correct 0 ms 200 KB OK (7 queries)
3 Correct 0 ms 200 KB OK (4 queries)
4 Correct 0 ms 200 KB OK (5 queries)
5 Correct 0 ms 200 KB OK (5 queries)
6 Correct 0 ms 284 KB OK (7 queries)
7 Correct 0 ms 200 KB OK (7 queries)
8 Correct 1 ms 200 KB OK (6 queries)
9 Correct 1 ms 200 KB OK (7 queries)
10 Correct 0 ms 200 KB OK (4 queries)
11 Correct 0 ms 200 KB OK (5 queries)
12 Correct 1 ms 200 KB OK (6 queries)
13 Correct 0 ms 200 KB OK (7 queries)
14 Correct 1 ms 284 KB OK (7 queries)
15 Correct 0 ms 200 KB OK (7 queries)
16 Correct 1 ms 200 KB OK (7 queries)
17 Correct 0 ms 200 KB OK (7 queries)
18 Correct 0 ms 200 KB OK (6 queries)
19 Correct 1 ms 200 KB OK (6 queries)
20 Correct 0 ms 200 KB OK (7 queries)
21 Correct 0 ms 200 KB OK (7 queries)
22 Correct 0 ms 200 KB OK (2 queries)
23 Correct 0 ms 200 KB OK (2 queries)
24 Correct 0 ms 200 KB OK (3 queries)
25 Correct 0 ms 200 KB OK (3 queries)
26 Correct 0 ms 200 KB OK (2 queries)
27 Correct 0 ms 200 KB OK (3 queries)
28 Correct 1 ms 200 KB OK (3 queries)
29 Correct 1 ms 200 KB OK (3 queries)
30 Correct 0 ms 200 KB OK (3 queries)
31 Correct 1 ms 200 KB OK (4 queries)
32 Correct 0 ms 200 KB OK (4 queries)
33 Correct 0 ms 200 KB OK (3 queries)
34 Correct 0 ms 200 KB OK (3 queries)
35 Correct 0 ms 200 KB OK (3 queries)
36 Correct 0 ms 200 KB OK (4 queries)
37 Correct 0 ms 200 KB OK (4 queries)
38 Correct 0 ms 200 KB OK (3 queries)
39 Incorrect 0 ms 200 KB Hair color 5 was used multiple times
40 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB OK (4 queries)
2 Correct 0 ms 200 KB OK (7 queries)
3 Correct 0 ms 200 KB OK (4 queries)
4 Correct 0 ms 200 KB OK (5 queries)
5 Correct 0 ms 200 KB OK (5 queries)
6 Correct 0 ms 284 KB OK (7 queries)
7 Correct 0 ms 200 KB OK (7 queries)
8 Correct 1 ms 200 KB OK (6 queries)
9 Correct 1 ms 200 KB OK (7 queries)
10 Correct 0 ms 200 KB OK (4 queries)
11 Correct 0 ms 200 KB OK (5 queries)
12 Correct 1 ms 200 KB OK (6 queries)
13 Correct 0 ms 200 KB OK (7 queries)
14 Correct 1 ms 284 KB OK (7 queries)
15 Correct 0 ms 200 KB OK (7 queries)
16 Correct 1 ms 200 KB OK (7 queries)
17 Correct 0 ms 200 KB OK (7 queries)
18 Correct 0 ms 200 KB OK (6 queries)
19 Correct 1 ms 200 KB OK (6 queries)
20 Correct 0 ms 200 KB OK (7 queries)
21 Correct 0 ms 200 KB OK (7 queries)
22 Correct 0 ms 200 KB OK (2 queries)
23 Correct 0 ms 200 KB OK (2 queries)
24 Correct 0 ms 200 KB OK (3 queries)
25 Correct 0 ms 200 KB OK (3 queries)
26 Correct 0 ms 200 KB OK (2 queries)
27 Correct 0 ms 200 KB OK (3 queries)
28 Correct 1 ms 200 KB OK (3 queries)
29 Correct 1 ms 200 KB OK (3 queries)
30 Correct 0 ms 200 KB OK (3 queries)
31 Correct 1 ms 200 KB OK (4 queries)
32 Correct 0 ms 200 KB OK (4 queries)
33 Correct 0 ms 200 KB OK (3 queries)
34 Correct 0 ms 200 KB OK (3 queries)
35 Correct 0 ms 200 KB OK (3 queries)
36 Correct 0 ms 200 KB OK (4 queries)
37 Correct 0 ms 200 KB OK (4 queries)
38 Correct 0 ms 200 KB OK (3 queries)
39 Incorrect 0 ms 200 KB Hair color 5 was used multiple times
40 Halted 0 ms 0 KB -