| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1290570 | amodi | Xylophone (JOI18_xylophone) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#include "xylophone.h"
#define int long long
static int A[5000];
map<int,bool>mp;
map<int,int>yer;
void solve(int n) {
pair<int,int>nve1;
int ans[105];
for(int i=2;i<=n;i++){
int x=query(i,n);
if(x!=n-1){
nve1.first=i-1;
break;
}
}
for(int i=n;i>=nve1.first-1;i--){
int x=query(nve1.first,i);
if(x!=n-1){nve1.second=i+1;
break;
}
}
ans[nve1.first]=1;
ans[nve1.second]=n;
int mn[105][105];
int mx[105][105];
for(int l=1;l<=n;l++){
for(int r=l;l<=n;l++) {
if(l<=nve1.first&&r>=nve1.first)mn[l][r]=1;
if(l<=nve1.second&&r>=nve1.second)mx[l][r]=n;
}
}
int mx1=-1e9;
int mn1=-1e9;
for(int i=nve1.first-1;i>0;i--) {
bool flag=0;
int deg=query(i,nve1.first);
deg++;
int r=nve1.first;
while(!mp[deg]) {
if(!flag){
mx[i][r]=deg;
r=ans[deg];
mx[i][r]=deg;
deg =query(i,r);
deg=mx[i+1][nve1.first]-deg;
}
else {
mn[i][r]=deg;
r=ans[deg];
mn[i][r]=deg;
deg =query(i,r);
deg=mn[i+1][nve1.first]+deg;
}
flag=!flag;
}
ans[deg]=i;
}
//sınır
for(int i=nve1.first+1;i<nve1.second;i++) {
bool flag=0;
int deg=query(nve1.first,i);
deg++;
int l=nve1.first;
while(!mp[deg]) {
if(!flag){
mx[l][i]=deg;
l=ans[deg];
mx[l][i]=deg;
deg =query(l,i);
deg=mx[l][i+1]-deg;
}
else {
mn[l][i]=deg;
l=ans[deg];
mn[l][i]=deg;
deg =query(l,i);
deg=mn[l][i]+deg;
}
flag=!flag;
}
ans[deg]=i;
}
//sınır
for(int i=nve1.second+1;i<=n;i++) {
bool flag=0;
int deg=query(nve1.second,i);
deg=n-deg;
int l=nve1.second;
while(!mp[deg]) {
if(!flag){
mx[l][i]=deg;
l=ans[deg];
mx[l][i]=deg;
deg =query(l,i);
deg=mx[l][i]+deg;
}
else {
mn[l][i]=deg;
l=ans[deg];
mn[l][i]=deg;
deg =query(l,i);
deg=mn[l][i]-deg;
}
flag=!flag;
}
ans[deg]=i;
}
for(int i=1;i<=n;i++) {
answer(i,ans[i]);
}
}