QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#233913 | #1968. Science Fiction | qzzyq | WA | 0ms | 3840kb | C++14 | 1.6kb | 2023-11-01 08:26:25 | 2023-11-01 08:26:25 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 10005
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &x){
int f=1;x=0;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
x*=f;
}
namespace Debug{
Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
int sum=1;
while (y) {
if (y&1) sum=sum*x%mod;
x=x*x%mod;y>>=1;
}
return sum;
}
int n,a[maxn],N;
pair<int,int>ans[100005];
int cnt,id[maxn],rk[maxn],c[maxn];
bool cmp(int x,int y) {return a[x]<a[y];}
void move(int x,int y) {swap(a[x],a[y]),swap(rk[x],rk[y]),ans[++cnt]=mk(x,y);}
void solve(int l,int r,int d) {
if (l==r) return ;
// gdb(l,r,d);
int mid=l+r>>1,tot=0,i;
for (i=l;i<=mid;i++) if ((rk[i]>>d)%2) c[++tot]=i;
for (i=mid+1;i<=r;i++) if ((rk[i]>>d)%2==0) move(i,c[tot--]);
assert(tot==0);
solve(l,mid,d-1);
solve(mid+1,r,d-1);
}
signed main(void){
int i;
read(n);N=(1<<n);
for (i=0;i<N;i++) read(a[i]),id[i]=i;
sort(id,id+N,cmp);
for (i=0;i<N;i++) rk[id[i]]=i;
solve(0,N-1,n-1);
for (i=0;i<N;i++) assert(rk[i]==i);
printf("%d\n",cnt);
for (i=1;i<=cnt;i++) printf("%d %d\n",ans[i].fi,ans[i].se);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3776kb
input:
2 3 2 10 4
output:
2 1 0 3 2
result:
ok nice! 2 moves
Test #2:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
1 10 100
output:
0
result:
ok nice! 0 moves
Test #3:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
1 824838 992401
output:
0
result:
ok nice! 0 moves
Test #4:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
2 208395 17211 250690 874014
output:
1 1 0
result:
ok nice! 1 moves
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3840kb
input:
8 991318 655714 983340 496226 752852 888298 572661 729100 426124 437775 8096 28612 303846 295897 970760 179029 702449 407420 945406 352294 960516 484993 724888 495235 156841 451864 95506 869159 61631 296168 279240 260130 901551 726353 298872 221580 982372 394731 720187 656498 595457 381795 759187 36...
output:
498 129 125 130 124 131 123 133 122 134 121 137 120 138 119 140 118 141 115 144 114 145 112 148 111 149 108 150 107 152 106 153 105 155 104 157 103 159 102 160 101 163 97 167 93 170 91 171 88 175 87 178 86 179 85 180 84 185 83 186 80 190 79 192 78 193 75 194 74 195 72 197 70 200 67 203 66 205 63 206...
result:
wrong answer invalid swap pair