Submission #1013694

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013694		vjudge1	Xylophone (JOI18_xylophone)	C++17	47 / 100	368 ms	592 KiB

xylophone

#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 int A[N_MAX];
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
void solve(int N) {
	int n=N;
	vector<int> ans(n+1);
	int l=1;
	int r=n-1;
	int pos=-1;
	while(l<=r){
		int mid=(l+r)/2;
		if(query(mid,n)==n-1){
			pos=mid;
			l=mid+1;
		}else{
			r=mid-1;
		}
	}
	bool visited[n+1];
	memset(visited,false,sizeof(visited));
	ans[pos]=1;
	visited[1]=1;
	if(pos!=n){
		ans[pos+1]=query(pos,pos+1)+1;//b-a=q => b=q+a
		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=query(i-2,i);
			int y=query(i-1,i);
			for(int c=1;c<=n;c++){
				if(visited[c]) continue;
				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){
					ans[i]=c;
					visited[ans[i]]=1;
					break;
				}
			}
		}
	}
	if(pos!=1){
		ans[pos-1]=query(pos-1,pos)+1;
		for(int i=pos-2;i>=1;i--){
			int a=ans[i+2];
			int b=ans[i+1];
			int x=query(i,i+2);
			int y=query(i,i+1);
			for(int c=1;c<=n;c++){
				if(visited[c]) continue;
				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){
					ans[i]=c;
					visited[ans[i]]=1;
					break;
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		answer(i,ans[i]);
	}
	// 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

Compilation message (stderr)

xylophone.cpp:25:12: warning: 'A' defined but not used [-Wunused-variable]
   25 | static int A[5000];
      |            ^

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