| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1013705 | vjudge1 | Xylophone (JOI18_xylophone) | C++17 | 0 ms | 0 KiB |
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 <bits/stdc++.h>
using namespace std;
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
#define endl "\n"
const int mod=1e9+7;
#define OVL(x,s) for(auto y:x) cout<<y<<s; cout<<"\n";
template <typename T> istream& operator>>(istream& is, vector<T> &a) {
copy_n(istream_iterator<T>(is), a.size(), a.begin()); return is;}
#ifdef IOI
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
#else
#define dbg(...) 1337;
#endif
#define pb push_back
#define F first
#define S second
#define all(v) v.begin(),v.end()
const int mxn=2e5+100;
static int A[5000];
#ifdef IOI
static const int N_MAX = 5000;
static const int Q_MAX = 10000;
static int N;
static bool used[N_MAX];
static int query_c;
static int answer_c;
int query(int s, int t) {
if(query_c >= Q_MAX) {
printf("Wrong Answer\n");
exit(0);
}
query_c++;
if(!(1 <= s && s <= t && t <= N)) {
printf("Wrong Answer\n");
exit(0);
}
int mx = 0, mn = N + 1;
for(int i = s - 1; i < t; i++) {
if(mx < A[i]) {
mx = A[i];
}
if(mn > A[i]) {
mn = A[i];
}
}
return mx - mn;
}
void answer(int i, int a) {
answer_c++;
if(!(1 <= i && i <= N)) {
printf("Wrong Answer\n");
exit(0);
}
if(!(1 <= a && a <= N)) {
printf("Wrong Answer\n");
exit(0);
}
if(used[i - 1]) {
printf("Wrong Answer\n");
exit(0);
}
if(a != A[i - 1]) {
printf("Wrong Answer\n");
exit(0);
}
used[i - 1] = true;
}
#endif
map<pair<int,int>,int> mp;
int q(int l,int r){
if(mp.count({l,r})) return mp[{l,r}];
return mp[{l,r}]=query(l,r);
}
vector<int> solve(int pos,int n){
bool visited[n+1];
vector<int> ans(n+1);
memset(visited,false,sizeof(visited));
ans[pos]=1;
visited[1]=1;
auto check = [&](int a,int b,int c,int x,int y){
vector<int> v={a,b,c};
sort(all(v));
vector<int> t={b,c};
sort(all(t));
if(v[2]-v[0]==x&&t[1]-t[0]==y){
return 1;
}else return 0;
};
if(pos!=n){
ans[pos+1]=q(pos,pos+1)+1;
visited[ans[pos+1]]=1;
for(int i=pos+2;i<=n;i++){
int a=ans[i-2];
int b=ans[i-1];
int x=q(i-2,i);
int y=q(i-1,i);
if(max(a,b)-min(a,b)==x){
//donc min(a,b)<c<max(a,b)
if(a>=b){
ans[i]=y+b;
}else{
ans[i]=b-y;
}
if(ans[i]<0||ans[i]>n) return {-1};
if(visited[ans[i]]){
return {-1};
}
visited[ans[i]]=1;
}else{
//c is either min or max
int c1=y+b;
int c2=y-b;
// dbg(c1,c2)
if(check(a,b,c1,x,y)&&c1>=1&&c1<=n){
if(visited[c1]){
return {-1};
}
visited[c1]=true;
ans[i]=c1;
}else if(check(a,b,c2,x,y)&&c2>=1&&c2<=n){
if(visited[c2]){
return {-1};
}
visited[c2]=true;
ans[i]=c2;
}else return {-1};
}
}
}
if(pos!=1){
ans[pos-1]=q(pos-1,pos)+1;
for(int i=pos-2;i>=1;i--){
int a=ans[i+2];
int b=ans[i+1];
int x=q(i,i+2);
int y=q(i,i+1);
if(max(a,b)-min(a,b)==x){
//donc min(a,b)<c<max(a,b)
if(a>=b){
ans[i]=y+b;
}else{
ans[i]=b-y;
}
if(ans[i]<0||ans[i]>n) return {-1};
if(visited[ans[i]]){
return {-1};
}
visited[ans[i]]=1;
}else{
//c is either min or max
int c1=y+b;
int c2=y-b;
if(check(a,b,c1,x,y)&&c1>=1&&c1<=n){
if(visited[c1]){
return {-1};
}
visited[c1]=true;
ans[i]=c1;
}else if(check(a,b,c2,x,y)&&c2>=1&&c2<=n){
if(visited[c2]){
return {-1};
}
visited[c2]=true;
ans[i]=c2;
}else return {-1};
}
}
}
return ans;
}
void solve(int N) {
vector<int> ans;
for(int i=1;i<=N;i++){
ans=solve(i,N);
// dbg(i,ans)
if(ans.size()==1) continue;
for(int i=1;i<=N;i++){
answer(i,ans[i]);
}
return;
}
// dbg(ans)
}
#ifdef IOI
int main() {
query_c = 0;
answer_c = 0;
if(scanf("%d", &N) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
for(int i = 0; i < N; i++) {
if(scanf("%d", A + i) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
used[i] = false;
}
solve(N);
if(!(answer_c == N)) {
printf("Wrong Answer\n");
exit(0);
}
printf("Accepted : %d\n", query_c);
}
#endif