| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 234679 | Nodir_Bobiev | Xylophone (JOI18_xylophone) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "xylophone.h"
int diff2[5555], diff3[5555], ans[5555], cnt[5555];
bool please_do_it(int idx, int N){
ans[idx] = N;
if( idx != 1 )
ans[idx-1] = N - diff2[idx-1];
if( idx != N )
ans[idx+1] = N - diff2[idx];
for( int i = idx-2; i >= 1; i -- ){
int val1 = diff2[i];
int val2 = diff3[i];
if( ans[i+1] < ans[i+2] ){
if( ans[i+2]-ans[i+1] > val1 and val2 == ans[i+2] - ans[i+1]){
ans[i] = ans[i+1] + val1;
}
else if( val2 > val1 ){
ans[i] = ans[i+1] - val1;
}
else{
ans[i] = ans[i+1] + val1;
}
}else{
if( ans[i+1]-ans[i+2] > val1 and val2 == ans[i+1] - ans[i+2]){
ans[i] = ans[i+1] - val1;
}
else if( val2 > val1 ){
ans[i] = ans[i+1] + val1;
}
else{
ans[i] = ans[i+1] - val1;
}
}
}
for( int i = idx+2; i <= N; i ++ ){
int val1 = diff2[i-1];
int val2 = diff3[i-2];
if( ans[i-2] > ans[i-1] ){
if( ans[i-2] - ans[i-1] > val1 and val2 == ans[i-2] - ans[i-1]){
ans[i] = ans[i-1] + val1;
}
else if( val2 > val1 ){
ans[i] = ans[i-1] - val1;
}else{
ans[i] = ans[i-1] + val1;
}
}else{
if( ans[i-1]-ans[i-2] > val1 and val2 == ans[i-1] - ans[i-2] ){
ans[i] = ans[i-1] - val1;
}
else if( val2 > val1 ){
ans[i] = ans[i-1] + val1;
}else{
ans[i] = ans[i-1] - val1;
}
}
}
int cnt[5555] = {} one = false;
for( int i = 1; i <= N; i ++ ){
if( ans[i] > N || ans[i] < 1)return false;
cnt[ans[i]] ++;
if( cnt[ans[i]]>1) return false;
if( ans[i] == 1 )one = true;
if( ans[i] == N && !one )return false;
}
return true;
}
void solve(int N) {
for( int i = 1; i <= N-1; i ++ ){
diff2[i] = query(i, i+1);
}
for( int i = 1; i <= N-2; i ++ ){
diff3[i] = query(i, i + 2 );
}
for( int i = 1; i <= N; i ++ ){
if( please_do_it(i, N) ){
/*
for( int i = 1; i <= N; i ++ ){
printf("%d ", ans[i]);
}printf("\n");
*/
for( int i = 1; i <= N; i ++ ){
answer(i, ans[i]);
}
return;
}
}
}