oj.uz

Submission #650497

# Submission time Handle Problem Language Result Execution time Memory
650497 2022-10-14T06:40:42 Z Koful123 Xylophone (JOI18_xylophone) C++17
0 / 100
 1 ms 336 KB 
#include <bits/stdc++.h>
#include <xylophone.h>
using namespace std;

void solve(int n){
	int l = 1,r = n;
	vector<int> v(n+1),th(n+1),se(n+1),vis(n+1,0);
	while(l < r){
		int m = (l + r) / 2;
		if(query(1,m) == n-1) r = m;
		else l = m + 1;
	}		
	v[l] = n; vis[n] = 1;
	if(l != n){
		se[l+1] = query(l,l+1);
		v[l+1] = n - se[l+1]; vis[v[l+1]] = 1;
	}

	for(int i=l+2;i<=n;i++){
		se[i] = query(i-1,i);
		if(v[i-1] + se[i] > n){
			v[i] = v[i-1] - se[i]; vis[v[i]] = 1; continue;
		}
		if(v[i-1] - se[i] <= 0){
			v[i] = v[i-1] + se[i]; vis[v[i]] = 1; continue;
		}
		if(vis[v[i-1] - se[i]]){
			v[i] = v[i-1] + se[i]; vis[v[i]] = 1; continue;
		}
		if(vis[v[i-1] + se[i]]){
			v[i] = v[i-1] - se[i]; vis[v[i]] = 1; continue;
		}
		th[i] = query(i-2,i);
		if(th[i] == se[i-1]){
			v[i] = v[i-1] + (v[i-2] > v[i-1] ? se[i] : -se[i]);
		}
		else{
			if(v[i-2] > v[i-1]){
				if(se[i] == th[i]) v[i] = v[i-1] + se[i];
				else v[i] = v[i-1] - se[i];
			}
			else{
				if(th[i] == se[i]) v[i] = v[i-1] - se[i];
				else v[i] = v[i-1] + se[i];;
			}
		}
		vis[v[i]] = 1;
	}

	if(l != 1){
		se[l-1] = query(l-1,l);
		v[l-1] = n - se[l-1]; vis[v[l-1]] = 1; 
	}

	for(int i=l-2;i>=1;i--){
		se[i] = query(i,i+1);

		if(v[i+1] + se[i] > n){
			v[i] = v[i+1] - se[i]; vis[v[i]] = 1; continue;
		}
		if(v[i+1] - se[i] <= 0){
			v[i] = v[i+1] + se[i]; vis[v[i]] = 1; continue;
		}
		if(vis[v[i+1] - se[i]]){
			v[i] = v[i+1] + se[i]; vis[v[i]] = 1; continue;
		}
		if(vis[v[i-1] + se[i]]){
			v[i] = v[i+1] - se[i]; vis[v[i]] = 1; continue;
		}

		th[i] = query(i,i+2);
		if(th[i] == se[i+1]){
			v[i] = v[i+1] + (v[i+2] > v[i+1] ? se[i] : -se[i]);
		}
		else{
			if(v[i+2] > v[i+1]){
				if(se[i] == th[i]) v[i] = v[i+1] + se[i];
				else v[i] = v[i+1] - se[i];
			}
			else{
				if(th[i] == se[i]) v[i] = v[i+1] - se[i];
				else v[i] = v[i+1] + se[i];
			}
		}
		vis[v[i]] = 1;
	}
	for(int i=1;i<=n;i++){
		assert(vis[i]);
		answer(i,v[i]);
	}
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Runtime error 1 ms 336 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Runtime error 1 ms 336 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Runtime error 1 ms 336 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -