oj.uz

Submission #996168

# Submission time Handle Problem Language Result Execution time Memory
996168 2024-06-10T08:25:29 Z anHiep Xylophone (JOI18_xylophone) C++14
0 / 100
 1 ms 2392 KB 
#include <bits/stdc++.h>
#include "xylophone.h"

using namespace std;

// static int a[5000];

int a[5004];
int mp[5004][5004];

void solve(int n) {

	// int value = query(1, N);

	// for(int i = 1; i <= N; i++) {
	// 	answer(i, i);
	// }
	int dis = query(1,2);
  mp[1][2]=dis;
	// map<pair<int,int>,int> mp;
	for(int i = 3; i <= n; i++){
		mp[i-1][i] = query(i-1, i);
		mp[i-2][i] = query(i-2, i);
	}
	for(int i = 1; i <= n; i++){
		a[1] = i;
		bool c = 1;
		if(i + dis <= n){
			c = 1;
			a[2] = i + dis;
			vector<int> used(n+1,0);
			used[a[1]] = 1;
			used[a[2]] = 2;

			for(int j = 3; j <= n; j++){
				int x = a[j-1] - mp[j-1][j];
				if(x >= 1 && used[x] == 0){
					if((max({x,a[j-1],a[j-2]})-min({x,a[j-1],a[j-2]})==mp[j-2][j]) && (max(x,a[j-1]) - min(x,a[j-1])==mp[j-1][j])){
						a[j] = x;
						used[x] = j;
						continue;
					}
				}
				x = a[j-1] + mp[j-1][j];
				if(x <= n && used[x] == 0){
					if((max({x,a[j-1],a[j-2]})-min({x,a[j-1],a[j-2]})==mp[j-2][j]) && (max(x,a[j-1]) - min(x,a[j-1])==mp[j-1][j])){
						a[j] = x;
						used[x] = j;
						continue;
					}
				}
				c = 0;
			}
			if(c){ 
				bool cc= 1;
				if(used[1]>used[n])continue;
				for(int j = 1;j<=n;j++){
					if(used[j]==0) cc = 0;
				}
				if(cc==0) continue;

				for(int j = 1;j<=n;j++){
					// cout<<a[j]<<" ";
					answer(j,a[j]);
				}
				// cout<<endl;
				return;
			}
		}
		if(i - dis >= 1){
			c = 1;
			a[2] = i - dis;
			vector<int> used(n+1,0);
			used[a[1]] = 1;
			used[a[2]] = 2;
			for(int j = 3;j<=n;j++){
				int x = a[j-1] - mp[j-1][j];
				if(x >= 1 && used[x] == 0){
					if((max({x,a[j-1],a[j-2]})-min({x,a[j-1],a[j-2]})==mp[j-2][j]) && (max(x,a[j-1]) - min(x,a[j-1])==mp[j-1][j])){
						a[j] = x;
						used[x] = j;
						continue;
					}
				}
				x = a[j-1] + mp[j-1][j];
				if(x <= n && used[x] == 0){
					if((max({x,a[j-1],a[j-2]})-min({x,a[j-1],a[j-2]})==mp[j-2][j]) && (max(x,a[j-1]) - min(x,a[j-1])==mp[j-1][j])){
						a[j] = x;
						used[x] = j;
						continue;
					}
				}
				c = 0;
			}
			if(c){
				bool cc = 1;
				for(int j = 1;j<=n;j++){
					if(used[j]==0) cc = 0;
				}
				if(cc==0) continue;
				if(used[1]>used[n]) continue;
				for(int j = 1;j<=n;j++){
					// cout<<a[j]<<" ";
					answer(j,a[j]);
				}
				// cout<<endl;
				return;
			}
		}
	}

}

Subtask #1
0 / 11.0

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

Subtask #2
0 / 36.0

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

Subtask #3
0 / 53.0

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