Submission #503959

#	Time	Username	Problem	Language	Result	Execution time	Memory
503959		Abrar_Al_Samit	Xylophone (JOI18_xylophone)	C++17	0 / 100	1 ms	200 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
 
void solve(int N) {
  int p = 1;
  int r = N;
  while(p<r) {
    int m = (p+r+1)/2;
    if(query(m, N)==N-1) p = m;
    else r = m-1;
  }
  set<int>revealed;
  revealed.insert(1);
  int ans[N+1];
  ans[p] = 1;

  if(p!=1) {
    ans[p-1] = query(p-1, p);
  }

  for(int i=p-2; i>0; --i) {
    int x = query(i, i+1);
    if(revealed.count(ans[i+1]+x)) {
      ans[i] = ans[i+1]-x;
    } else if(revealed.count(ans[i+1]-x)) {
      ans[i] = ans[i+1]+x;
    } else {
      //grey
      int y = query(i, i+2);
      if(ans[i+1]>ans[i+2]) {
        if(y==ans[i+1]-ans[i+2]+x) {
          ans[i] = ans[i+1]+x;
        } else {
          ans[i] = ans[i+1]-x;
        }
      } else {
        if(y==ans[i+2]-ans[i+1]+x) {
          ans[i] = ans[i+1]-x;
        } else {
          ans[i] = ans[i+1]+x;
        }
      }
    }
    revealed.insert(ans[i]);
  }
  ans[p+1] = query(p, p+1)+1;
  for(int i=p+2; i<=N; ++i) {
    int x = query(i-1, i);
    if(revealed.count(ans[i-1]+x)) {
      ans[i] = ans[i-1]-x;
    } else if(revealed.count(ans[i-1]-x)) {
      ans[i] = ans[i-1]+x;
    } else {
      //grey
      int y = query(i-2, i);
      if(ans[i-1]>ans[i-2]) {
        if(y==ans[i-1]-ans[i-2]+x) {
          ans[i] = ans[i-1]+x;
        } else {
          ans[i] = ans[i-1]-x;
        }
      } else {
        if(y==ans[i-2]-ans[i-1]+x) {
          ans[i] = ans[i-1]-x;
        } else {
          ans[i] = ans[i-1]+x;
        }
      }
    }
    revealed.insert(ans[i]);
  }

  for(int i=1; i<=N; ++i) {
    answer(i, ans[i]);
  }
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 36
• Subtask 3: 0 / 53