QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#233912#1968. Science FictionqzzyqWA 1ms3592kbC++141.6kb2023-11-01 08:25:212023-11-01 08:25:21

Judging History

你现在查看的是最新测评结果

  • [2023-11-01 08:25:21]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3592kb
  • [2023-11-01 08:25:21]
  • 提交

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);
	printf("%d\n",cnt);
	for (i=1;i<=cnt;i++) printf("%d %d\n",ans[i].fi,ans[i].se);
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3592kb

input:

2
3 2 10 4

output:

2
1 0
3 2

result:

ok nice! 2 moves

Test #2:

score: 0
Accepted
time: 1ms
memory: 3500kb

input:

1
10 100

output:

0

result:

ok nice! 0 moves

Test #3:

score: 0
Accepted
time: 0ms
memory: 3544kb

input:

1
824838 992401

output:

0

result:

ok nice! 0 moves

Test #4:

score: 0
Accepted
time: 0ms
memory: 3536kb

input:

2
208395 17211 250690 874014

output:

1
1 0

result:

ok nice! 1 moves

Test #5:

score: -100
Wrong Answer
time: 1ms
memory: 3540kb

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