oj.uz

Submission #284241

# Submission time Handle Problem Language Result Execution time Memory
284241 2020-08-27T04:48:46 Z YJU Xylophone (JOI18_xylophone) C++14
0 / 100
 1 ms 384 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#include "xylophone.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=2e5+5;
const ld pi=3.14159265359;
const ll INF=(1LL<<60);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()

ll vis[N],ans[N],low=0;

void solve(int n){
	for(ll i=18;i>=0;i--){
		if(low+(1LL<<i)>=n)continue;
		if(query(low+(1LL<<i),n)==n-1){
			low+=(1LL<<i);
		}
	}
	vis[ans[low]=1]=1;
	for(ll i=low;i<n;i++){
		ll d=query(i,i+1);
		if(ans[i]+d>n||vis[ans[i]+d]){ans[i+1]=ans[i]-d;vis[ans[i+1]]=1;continue;}
		if(ans[i]-d<1||vis[ans[i]-d]){ans[i+1]=ans[i]+d;vis[ans[i+1]]=1;continue;}
		ll D=query(i-1,i+1);
		if(D==d+abs(ans[i]-ans[i-1])){
			ans[i+1]=(ans[i]>ans[i-1]?ans[i]+d:ans[i]-d);
			vis[ans[i+1]]=1;continue;
		}else{
			ans[i+1]=(ans[i]>ans[i-1]?ans[i]-d:ans[i]+d);
			vis[ans[i+1]]=1;continue;
		}
	}
	for(ll i=low;i>1;i--){
		ll d=query(i,i-1);
		if(ans[i]+d>n||vis[ans[i]+d]){ans[i-1]=ans[i]-d;vis[ans[i-1]]=1;continue;}
		if(ans[i]-d<1||vis[ans[i]-d]){ans[i-1]=ans[i]+d;vis[ans[i-1]]=1;continue;}
		ll D=query(i-1,i+1);
		if(D==d+abs(ans[i]-ans[i+1])){
			ans[i-1]=(ans[i]>ans[i+1]?ans[i]+d:ans[i]-d);
			vis[ans[i-1]]=1;continue;
		}else{
			ans[i-1]=(ans[i]>ans[i+1]?ans[i]-d:ans[i]+d);
			vis[ans[i-1]]=1;continue;
		}
	}
	REP1(i,n)answer(i,ans[i]);
	return;
}

Subtask #1
0 / 11.0

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

Subtask #2
0 / 36.0

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

Subtask #3
0 / 53.0

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