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 "xylophone.h"
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
int N;
int A[5000];
bool used[5000];
int cache[5000][5000];
bool ok(int x) {
return x>=0 && x<N && !used[x];
}
void setA(int pos, int val) {
assert(!used[val]);
used[val] = true;
A[pos] = val;
}
int ask(int l, int r) {
if (l > r) swap(l, r);
if (l == r) return 0;
if (cache[l][r]) return cache[l][r];
return cache[l][r] = query(l+1, r+1);
}
void solve(int NN) {
N = NN;
int lo = 0, hi = N-1;
while (hi-lo > 1) {
int mid = (lo+hi)/2;
if (ask(0, mid) == N-1) hi = mid;
else lo = mid;
}
rep(i, N) A[i] = -1;
setA(hi, N-1);
setA(hi-1, N-1-ask(hi-1, hi));
for (int i=hi+1; i<N; i++) {
//cout<<A[i-2]<<","<<A[i-1]<<",?\n";
int d = ask(i-1, i);
vector<int> qs;
if (ok(A[i-1]+d)) qs.pb(A[i-1]+d);
if (ok(A[i-1]-d)) qs.pb(A[i-1]-d);
if (qs.size()==2) {
vector<int> nqs;
for (int x : qs) {
if (max(x, A[i-2])-min(x, A[i-2]) == ask(i-2, i)) nqs.pb(x);
}
swap(qs, nqs);
}
assert(qs.size() == 1);
setA(i, qs[0]);
}
for (int i=hi-2; i>=0; i--) {
int d = ask(i, i+1);
vector<int> qs;
if (ok(A[i+1]+d)) qs.pb(A[i+1]+d);
if (ok(A[i+1]-d)) qs.pb(A[i+1]-d);
if (qs.size()==2) {
vector<int> nqs;
for (int x : qs) {
if (max(x, A[i+2])-min(x, A[i+2]) == ask(i, i+2)) nqs.pb(x);
}
swap(qs, nqs);
}
assert(qs.size() == 1);
setA(i, qs[0]);
}
//rep(i, N) cout << A[i]<<",";cout<<"\n";
rep(i, N) answer(i+1, A[i]+1);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |