oj.uz

답안 #1070509

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1070509 2024-08-22T14:52:13 Z _8_8_ Xylophone (JOI18_xylophone) C++17
0 / 100
 26 ms 98392 KB 
#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
int p[5002],a[5002],mem[5002][5002];
int QQ(int l,int r) {
	if(mem[l][r] != -1) {
		return mem[l][r];
	}
	return mem[l][r] = query(l,r);
}
int n_;
bool bad(int x) {
	return (x < 1 || x > n_ || p[x]);
}
void make(int v,int val) {
	a[v] = val;
	p[val] = v;
}
void solve(int n) {
	n_ = n;
	memset(mem,-1,sizeof(mem));
	memset(p,0,sizeof(p));
	memset(a,0,sizeof(a));
	int nd = n - 1;
	int l = 1,r = n;
	while(r - l > 1) {
		int mid = (l + r) >> 1;
		if(QQ(1,mid) == nd) {
			r = mid;
		} else {
			l = mid;
		}
	}
	p[n] = r;
	l = 1,r = p[n];
	while(r - l > 1) {
		int mid = (l + r) >> 1;
		if(QQ(mid,p[n]) == nd) {
			l = mid;
		} else {
			r = mid;
		}
	}
	p[1] = l;
	a[p[1]] = 1;
	a[p[n]] = n;
	int mx = 1;
	if(p[1] - 1 >= 1) {
		make(p[1] - 1,1 + QQ(p[1] - 1,p[1]));
	}
	for(int i = p[1] - 2;i >= 1;i--) {
		int t2, t1, val;
		int t = QQ(i,i + 1);
		if(bad(a[i + 1] + t))  {
			val = a[i + 1] - t;
		} else if(bad(a[i + 1] - t)) {
			val = a[i + 1] + t;
		}
		else {
			t2 = QQ(i,i + 2);
			t1 = QQ(i + 1,i + 2);
			if(a[i + 2] > a[i + 1]) {
				if(t2 == a[i + 2] - (a[i + 1] - t)) {
					val = a[i + 1] - t;
				} else {
					val = a[i + 1] + t;
				}
			} else {
				if(t2 == a[i + 1] + t - a[i + 2]) {
					val = a[i + 1] + t;
				} else {
					val = a[i + 1] - t;
				}
			}
		}
		// cout << i << ' ' << val << ' ' << (a[i + 2] > a[i + 1]) << '\n';
		p[val] = i;
		a[i] = val;
	}
	mx = 1;
	if(p[1] + 1 < p[n]) {
		make(p[1] + 1,1 + QQ(p[1],p[1]+1));
	}
	for(int i = p[1] + 2;i < p[n];i++) {
		int val, T;
		T = QQ(p[1],i);	
		if(T != mx - 1) {
			val = mx = 1 + T;
		} else {
			int t2, t1;
			int t = QQ(i - 1,i);
			if(bad(a[i - 1] + t))  {
				val = a[i - 1] - t;
			} else if(bad(a[i - 1] - t)) {
				val = a[i - 1] + t;
			} else{
				t2 = QQ(i - 2,i);
				t1 = QQ(i - 2,i - 1);
				if(a[i - 2] > a[i - 1]) {
					if(t2 == a[i - 2] - (a[i - 1] - t)) {
						val = a[i - 1] - t;
					} else {
						val = a[i - 1] + t;
					}
				} else {
					if(t2 == a[i - 1] + t - a[i - 2]) {
						val = a[i - 1] + t;
					} else {
						val = a[i - 1] - t;
					}
				}
			}
		}
		// cout << i << ' ' << val << '\n';
		p[val] = i;
		a[i] = val;
	}
	int mn = n;
	for(int i = p[n] + 1;i <= n;i++) {
		int val, T = QQ(p[n],i);
		if(T != n - mn) {
			mn = val = n - T;
		} else {
			int t2, t1;
			int t = QQ(i - 1,i);
			if(bad(a[i - 1] + t))  {
				val = a[i - 1] - t;
			} else if(bad(a[i - 1] - t)) {
				val = a[i - 1] + t;
			} else{
				t2 = QQ(i - 2,i);
				t1 = QQ(i - 2,i - 1);
				if(a[i - 2] > a[i - 1]) {
					if(t2 == a[i - 2] - (a[i - 1] - t)) {
						val = a[i - 1] - t;
					} else {
						val = a[i - 1] + t;
					}
				} else {
					if(t2 == a[i - 1] + t - a[i - 2]) {
						val = a[i - 1] + t;
					} else {
						val = a[i - 1] - t;
					}
				}
			}
		}
		p[val] = i;
		a[i] = val;
	}
	for(int i = 1;i <= n;i++) {
		answer(p[i],i);
	}
}

Compilation message

xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:52:11: warning: variable 't1' set but not used [-Wunused-but-set-variable]
   52 |   int t2, t1, val;
      |           ^~
xylophone.cpp:90:12: warning: variable 't1' set but not used [-Wunused-but-set-variable]
   90 |    int t2, t1;
      |            ^~
xylophone.cpp:124:12: warning: variable 't1' set but not used [-Wunused-but-set-variable]
  124 |    int t2, t1;
      |            ^~

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 98392 KB Output is correct
2 Correct 25 ms 98128 KB Output is correct
3 Correct 25 ms 98392 KB Output is correct
4 Incorrect 25 ms 98252 KB Wrong Answer [3]
5 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 98392 KB Output is correct
2 Correct 25 ms 98128 KB Output is correct
3 Correct 25 ms 98392 KB Output is correct
4 Incorrect 25 ms 98252 KB Wrong Answer [3]
5 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 98392 KB Output is correct
2 Correct 25 ms 98128 KB Output is correct
3 Correct 25 ms 98392 KB Output is correct
4 Incorrect 25 ms 98252 KB Wrong Answer [3]
5 Halted 0 ms 0 KB -