| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 29936 | aybala | 동굴 (IOI13_cave) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "cave.h"
#include<bits/stdc++.h>
#define fori(a,b,c) for(int a=b; a<c; a++)
#define ford(a,b,c) for(int a=b; a>=c; a--)
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
int n;
int sw[5000];
#include "cave.h"
#include<bits/stdc++.h>
#define fori(a,b,c) for(int a=b; a<c; a++)
#define ford(a,b,c) for(int a=b; a>=c; a--)
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
int n;
int sw[5000];
int used[5000];
pii b[8900];
//pii a[8900];
int s[5000],d[5000];
void exploreCave(int N) {
n=N;
int lg=0;
while((1<<lg) < n){
lg++;
}
cout << lg;
int nn=(1<<lg);
fori(i,0,n){
int las=0;
fori(j,0,lg+1){
fori(k,las,las+(nn/(1<<j))){
if(k>=n)
break;
if(!used[k]){
sw[k]=(b[i].se+1)%2;
}
else{
sw[k]=s[k];
}
}
if(las>=n){
continue;
}
int trc=tryCombination(sw);
/*if(n==1){
if(trc!=i){
b[i].se=1;
}
d[i]=i;
s[i]=b[i].se;
}
if(j==lg){
if(trc!=i){
used[las+1]=1;
b[i].fi=las+1;
d[las+1]=i;
s[las+1]=b[i].se;
}
else{
used[las]=1;
b[i].fi=las;
d[las]=i;
s[las]=b[i].se;
}
break;
}
if(trc!=i && j==0){
b[i].se = 1;
continue;
}
if(trc==i && j==0){
fori(k,las,las+(nn/(1<<j))){
if(k>=n)
break;
if(!used[k]){
sw[k]=0;
}
else{
sw[k]=s[k];
}
}
continue;
}
if(trc!=i && j!=0){
if(las+(nn/(1<<j)) <n)
las=las+(nn/(1<<j));
continue;
}
if(trc==i && j!=0){
fori(k,las,las+(nn/(1<<j))){
if(k>=n)
break;
if(!used[k]){
sw[k]=(b[i].se)%2;
}
else{
sw[k]=s[k];
}
}
continue;
}
*/
}
}
/*fori(i,0,n){
s[i]=a[i].se;
d[i]=a[i].fi;
}*/
/*fori(i,0,80000){
tryCombination(sw);
}*/
answer(s,d);
return ;
}
int used[5000];
pii b[8900];
//pii a[8900];
int s[5000],d[5000];
void exploreCave(int N) {
n=N;
int lg=0;
while((1<<lg) < n){
lg++;
}
cout << lg;
int nn=(1<<lg);
fori(i,0,n){
int las=0;
int x=0;
fori(j,0,lg+1){
fori(k,las,las+(nn/(1<<j))+x){
if(k>=n)
break;
if(!used[k]){
sw[k]=(b[i].se+1)%2;
}
else{
sw[k]=s[k];
}
}
if(las>=n){
continue;
}
int trc=tryCombination(sw);
if(n==1){
if(trc!=i){
b[i].se=1;
}
d[i]=i;
s[i]=b[i].se;
}
if(j==lg){
if(trc!=i){
used[las+1]=1;
b[i].fi=las+1;
d[las+1]=i;
s[las+1]=b[i].se;
}
else{
used[las]=1;
b[i].fi=las;
d[las]=i;
s[las]=b[i].se;
}
break;
}
if(trc!=i && j==0){
b[i].se = 1;
continue;
}
if(trc==i && j==0){
fori(k,las,las+(nn/(1<<j))+x){
if(k>=n)
break;
if(!used[k]){
sw[k]=0;
}
else{
sw[k]=s[k];
}
}
continue;
}
if(trc!=i && j!=0){
if(las+(nn/(1<<(j)))+x <n)
las=las+(nn/(1<<j))+x;
continue;
}
if(trc==i && j!=0){
fori(k,las,las+(nn/(1<<j))+x){
if(k>=n)
break;
if(!used[k]){
sw[k]=(b[i].se)%2;
}
else{
sw[k]=s[k];
}
}
continue;
}
}
}
/*fori(i,0,n){
s[i]=a[i].se;
d[i]=a[i].fi;
}*/
/*fori(i,0,80000){
tryCombination(sw);
}*/
answer(s,d);
return ;
}