oj.uz

Submission #212305

# Submission time Handle Problem Language Result Execution time Memory
212305 2020-03-22T16:55:29 Z tselmegkh Xylophone (JOI18_xylophone) C++14
0 / 100
 5 ms 384 KB 
#include<bits/stdc++.h>
#include "xylophone.h"
using namespace std;
const int N = 1e5 + 5, inf = 1e9;

#define pb push_back
#define mp make_pair
#define ll long long
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

/*int query(int l, int r){
  cout << l << ' ' << r << endl;
  int res; cin >> res;
  return res;
}
void answer(int i, int x){
  cout << i << " = " << x << '\n';
}*/
void solve(int n){
  vi ans(n + 1);
  int s, t;
  int l = 1, r = n - 1;
  while(l != r){
    int mid = (l + r + 1) / 2;
    if(query(mid, n) < n - 1){
      r = mid - 1;
    }else{
      l = mid;
    }
  }
  s = l;
  l = s + 1, r = n;
  while(l != r){
    int mid = (l + r) / 2;
    if(query(s, mid) < n - 1){
      l = mid + 1;
    }else{
      r = mid;
    }
  }
  t = r;
  ans[s] = 1, ans[t] = n;
  int prev = -1;
  for(int i = t + 1; i <= n; i++){
    int res = n - query(t, i);
    int tmp = res;
    if(res == prev){
      res = ans[i - 1] + query(i - 1, i);
    }
    prev = tmp;
    ans[i] = res;
  }
  prev = -1;
  for(int i = s - 1; i >= 1; i--){
    int res = 1 + query(i, s);
    int tmp = res;
    if(res == prev){
      res = ans[i + 1] - query(i, i + 1);
    }
    prev = tmp;
    ans[i] = res;
  }
  for(int i = s + 1; i < t; i++){
    int res = 1 + query(s, i);
    int tmp = res;
    if(res == prev){
      res = ans[i - 1] - query(i - 1, i);
    }
    prev = tmp;
    ans[i] = res;
  }
  for(int i = 1; i <= n; i++){
    answer(i, ans[i]);
  }
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Incorrect 5 ms 384 KB Wrong Answer [4]
4 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Incorrect 5 ms 384 KB Wrong Answer [4]
4 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Incorrect 5 ms 384 KB Wrong Answer [4]
4 Halted 0 ms 0 KB -