oj.uz

답안 #763286

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
763286 2023-06-22T07:43:05 Z cheat_when_I_was_young Xylophone (JOI18_xylophone) C++17
0 / 100
 2 ms 592 KB 
#include "xylophone.h"
#include "bits/stdc++.h"
using namespace std;
int q[5005][5005], a[5005];
bool check_permutation(int n) {
    bool b[n+1];
    memset(b, 0, sizeof(b));
    for (int i = 1; i <= n; ++i) if (a[i] <= n) b[a[i]] = 1;
    for (int i = 1; i <= n; ++i) if (!b[i]) return false;
    for (int i = 1; i < n; ++i) if (abs(a[i+1] - a[i]) != q[i][i+1]) return false;
    for (int i = 1; i < n-1; ++i)
        if (max(a[i], max(a[i+1], a[i+2])) - min(a[i], min(a[i+1], a[i+2])) != q[i][i+2]) return false;
    return true;
}
void build_permutation(int n, int x, int y) {
    a[1] = x;
    a[2] = y;
    for (int i = 3; i <= n; ++i) {
		if (q[i-2][i-1] + q[i-1][i] == q[i-2][i]) {
			if (a[i-2] > a[i-1]) a[i] = a[i-1] - q[i-1][i];
			else a[i] = a[i-1] + q[i-1][i];
		} else {
			if (a[i-2] > a[i-1]) a[i] = a[i-1] + q[i-1][i];
			else a[i] = a[i-1] - q[i-1][i];
		}
	}
	int mi = *min_element(a+1, a+n+1) - 1;
	for (int i = 1; i <= n; ++i) a[i] -= mi;
}
void solve(int n) {
	for (int i = 1; i <= n-1; ++i) q[i][i+1] = q[i+1][i] = query(i, i+1);
	for (int i = 1; i <= n-2; ++i) q[i][i+2] = q[i+2][i] = query(i, i+2);
	int pos = 1;
	for (int i = 1<<12; i > 0; i >>= 1) {
		if (pos + i > n) continue;
		if (query(pos + i, n) == n - 1) pos += i;
	}
	for (int i = 1; i < n; ++i) {
	    build_permutation(n, 10000, 10000 + i);
	    if (check_permutation(n)) {
	        for (int i = 1; i <= n; ++i) answer(i, a[i]);
	        return;
	    }
	}
	for (int i = 1; i < n; ++i) {
	    build_permutation(n, 10000 + i, 10000);
	    if (check_permutation(n)) {
	        for (int i = 1; i <= n; ++i) answer(i, a[i]);
	        return;
	    }
	}
}

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Incorrect 2 ms 592 KB Wrong Answer [7]
6 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Incorrect 2 ms 592 KB Wrong Answer [7]
6 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Incorrect 2 ms 592 KB Wrong Answer [7]
6 Halted 0 ms 0 KB -