This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "xylophone.h"
using namespace std;
typedef long long ll;
typedef vector<int>vi;
#define pb push_back
#define sz(v) (int)v.size()
#define all(x) begin(x),end(x)
#define FOR(i,a,b) for(int i=a; i<b; i++)
#define ROF(i,a,b) for(int i=b-1; i>=a; i--)
//-----------------------------------------------------------//
#define tt t
int N;
const int MX=5e3+10;
unordered_map<int,int>mp[MX];
int get(int s, int t){
if(!mp[s].count(t)) mp[s][t]=query(s,t);
return mp[s][t];
}
int BS(){
int l=1,r=N-1,ans=1;
while(l<=r){
int m=(l+r)/2;
if(get(m,N)==N-1){
ans=m;
l=m+1;
}
else r=m-1;
}
return ans;
}
void solve(int N) {
::N=N;
int idx=BS();
vi a(N+1,-1);
//part 1
a[idx]=1;
a[idx+1]=get(idx,idx+1)+1;
int prev=a[idx+1]-1,ty=0,s=idx;
FOR(t,idx+1,N){
int x=get(s,t+1),y=get(t,t+1);
if(!ty){
if(x!=prev){
if(x!=y) a[t+1]=a[t]+y;
else a[t+1]=a[t]-y,ty=1,s=t;
}
else a[t+1]=a[t]-y,ty=1,s=t;
}
else{
if(x!=prev){
if(x!=y) a[t+1]=a[t]-y;
else a[t+1]=a[t]+y,ty=0,s=t;
}
else a[t+1]=a[t]+y,ty=0,s=t;
}
prev=get(s,t+1);
}
//part 2
if(idx>1){
a[idx-1]=get(idx-1,idx)+1;
prev=a[idx-1]+1,ty=0,s=idx;
ROF(t,2,idx){
int x=get(t-1,s),y=get(t-1,t);
if(!ty){
if(x!=prev){
if(x!=y) a[t-1]=a[t]+y;
else a[t-1]=a[t]-y,ty=1,s=t;
}
else a[t-1]=a[t]-y,ty=1,s=t;
}
else{
if(x!=prev){
if(x!=y) a[t-1]=a[t]-y;
else a[t-1]=a[t]+y,ty=0,s=t;
}
else a[t-1]=a[t]+y,ty=0,s=t;
}
prev=get(t-1,t);
}
}
//FOR(i,1,N+1) cout << a[i] << ' '; cout << endl;
FOR(i,1,N+1){
answer(i,a[i]);
}
}
/*
15
9 8 7 6 1 14 13 10 15 2 3 4 5 11 12
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |