UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#214239#2022. anullptr_qwq100171ms5460kbC++115.8kb2024-11-16 19:27:392024-11-16 23:11:26

answer

// 私は猫です

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define int long long
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
#define inf 1000000000
#define infll 1000000000000000000ll
#define pii pair<int,int>
#define rep(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define per(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define F(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define dF(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define cmh(sjy) while(sjy--)
#define lowbit(x) (x&(-x))
#define HH printf("\n")
#define eb emplace_back
#define poly vector<int>
#define SZ(x) ((int)x.size())
using namespace std;
ll read(){
	ll x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return x*f;
}
namespace Fastio{struct Reader{template<typename T>Reader&operator>>(T&x){x=0;short f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();x*=f;return*this;}Reader&operator>>(double&x){x=0;double t=0;short f=1,s=0;char c=getchar();while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else{x*=f;return*this;}while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}Reader&operator>>(long double&x){x=0;long double t=0;short f=1,s=0;char c=getchar();while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else{x*=f;return*this;}while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}Reader&operator>>(__float128&x){x=0;__float128 t=0;short f=1,s=0;char c=getchar();while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else{x*=f;return*this;}while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}Reader&operator>>(char&c){c=getchar();while(c==' '||c=='\n'||c=='\r')c=getchar();return*this;}Reader&operator>>(char*str){int len=0;char c=getchar();while(c==' '||c=='\n'||c=='\r')c=getchar();while(c!=' '&&c!='\n'&&c!='\r')str[len++]=c,c=getchar();str[len]='\0';return*this;}Reader&operator>>(string&str){str.clear();char c=getchar();while(c==' '||c=='\n'||c=='\r')c=getchar();while(c!=' '&&c!='\n'&&c!='\r')str.push_back(c),c=getchar();return*this;}Reader(){}}cin;const char endl='\n';struct Writer{const int Setprecision=6;typedef int mxdouble;template<typename T>Writer&operator<<(T x){if(x==0){putchar('0');return*this;}if(x<0)putchar('-'),x=-x;static short sta[40];short top=0;while(x>0)sta[++top]=x%10,x/=10;while(top>0)putchar(sta[top]+'0'),top--;return*this;}Writer&operator<<(double x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(double)_;static short sta[40];short top=0;while(_>0)sta[++top]=_%10,_/=10;if(top==0)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;putchar('.');for(int i=0;i<Setprecision;i++)x*=10;_=x;while(_>0)sta[++top]=_%10,_/=10;for(int i=0;i<Setprecision-top;i++)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;return*this;}Writer&operator<<(long double x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(long double)_;static short sta[40];short top=0;while(_>0)sta[++top]=_%10,_/=10;if(top==0)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;putchar('.');for(int i=0;i<Setprecision;i++)x*=10;_=x;while(_>0)sta[++top]=_%10,_/=10;for(int i=0;i<Setprecision-top;i++)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;return*this;}Writer&operator<<(__float128 x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(__float128)_;static short sta[40];short top=0;while(_>0)sta[++top]=_%10,_/=10;if(top==0)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;putchar('.');for(int i=0;i<Setprecision;i++)x*=10;_=x;while(_>0)sta[++top]=_%10,_/=10;for(int i=0;i<Setprecision-top;i++)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;return*this;}Writer&operator<<(char c){putchar(c);return*this;}Writer&operator<<(char*str){int cur=0;while(str[cur])putchar(str[cur++]);return*this;}Writer&operator<<(const char*str){int cur=0;while(str[cur])putchar(str[cur++]);return*this;}Writer&operator<<(string str){int st=0,ed=str.size();while(st<ed)putchar(str[st++]);return*this;}Writer(){}}cout;}using namespace Fastio;
#define cin Fastio::cin
#define cout Fastio::cout
#define endl Fastio::endl
template<typename T>inline void chkmax(T &x,const T &y){ x=std::max(x,y); }
template<typename T>inline void chkmin(T &x,const T &y){ x=std::min(x,y); }
const int mod=998244353,maxn=500005;
vector<pii>ans;
int lim,n,a[maxn],b[maxn];
mt19937 eng(std::chrono::steady_clock::now().time_since_epoch().count());
inline int rd(const int l,const int r) { return std::uniform_int_distribution<int>(l,r)(eng); }
void Sort_(int l,int r){
	if(l>=r)return;
	if(l==r-1){
		if(a[l]>lim&&a[r]<=lim)swap(a[l],a[r]),ans.push_back(mkp(l,r));
		return;
	}
	int mid=(l+r)>>1;
	Sort_(l,mid),Sort_(mid+1,r);
	if(a[mid]>lim&&a[mid+1]<=lim){
		int p=l,q=r;
		F(i,l,mid)if(a[i]>lim){ p=i; break; }
		F(i,mid+1,r)if(a[i]>lim){ q=i-1; break; }
		if(p&&q)ans.push_back(mkp(p,q)),reverse(a+p,a+q+1);
	}
}
void Solve(int l,int r,int dep=30){
	if(l>=r||dep<0)return;
	int x=0,y=0;
	F(i,l,r)if((a[i]>>dep)&1)x=1; else y=1;
	if(!x||!y){
		F(i,l,r)if((a[i]>>dep)&1)a[i]^=(1<<dep);
		return Solve(l,r,dep-1),void();
	}
	lim=(1<<dep)-1,Sort_(l,r);
	int pos=0;
	F(i,l,r)if(a[i]>lim){pos=i;break;}
	F(i,l,r)if(a[i]>lim)a[i]^=(1<<dep);
	Solve(l,pos-1,dep-1),Solve(pos,r,dep-1);
}
void solve(){
	cin>>n;
	F(i,1,n)cin>>a[i];
	Solve(1,n);
	cout<<SZ(ans)<<endl;
	F(i,0,SZ(ans)-1)cout<<ans[i].fi<<' '<<ans[i].se<<endl;
}
signed main(){
	// ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int zsy=1;
	F(____,1,zsy)solve();
}

Details

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 20
Accepted

Test #1:

score: 20
Accepted
time: 0ms
memory: 1192kb

input:

63
19732 30594 10113 7702 9784 6421 4697 13517 5317 8508 26509 15653 2986 31587 11246 12158 24378 49...

output:

160
1 4
3 8
11 12
14 16
12 15
7 14
17 18
22 23
18 22
27 28
26 27
29 30
30 31
27 30
20 28
13 23
33 35...

result:

ok ok,using 585 times

Test #2:

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

input:

25
21264 13876 11861 12802 18452 3136 17660 21163 14140 20632 25998 22051 10612 12680 7873 23249 274...

output:

49
1 2
2 4
5 6
4 5
8 9
11 13
9 11
5 9
20 22
24 25
21 24
16 22
7 18
1 4
7 8
8 9
9 10
2 9
3 4
2 3
1 2
...

result:

ok ok,using 145 times

Test #3:

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

input:

95
26373 31391 7777 12225 25301 24166 2461 4926 15751 18727 29175 18511 17455 16025 16845 6723 3477 ...

output:

278
1 3
2 4
3 9
13 14
14 17
22 23
23 24
20 23
16 21
6 18
25 26
32 33
26 32
44 45
46 47
47 48
45 47
3...

result:

ok ok,using 1063 times

Test #4:

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

input:

100
15104 1621 22502 12704 13109 9592 1390 22280 23468 26863 23084 10981 20492 7842 12883 16636 2565...

output:

278
3 4
4 7
11 12
8 11
7 8
17 18
16 17
21 22
23 24
24 25
22 24
17 23
8 20
26 28
27 31
33 34
34 35
36...

result:

ok ok,using 1105 times

Test #5:

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

input:

100
13822 19801 16537 25492 24250 30303 18588 13044 8538 23642 864 10878 16671 5509 13062 15457 2577...

output:

276
10 12
2 11
17 18
18 19
20 25
19 22
6 21
28 31
33 34
34 37
30 35
39 40
43 44
40 43
45 50
42 47
33...

result:

ok ok,using 1100 times

Subtask #2:

score: 40
Accepted

Test #6:

score: 40
Accepted
time: 0ms
memory: 1212kb

input:

197
10471 12679 10817 27406 21095 21068 9625 5396 14548 20977 29338 17674 30961 25672 4782 22715 301...

output:

613
5 7
4 5
5 9
14 15
20 21
21 22
15 21
7 16
26 27
27 29
30 32
29 30
34 35
37 38
35 37
30 36
39 41
4...

result:

ok ok,using 2733 times

Test #7:

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

input:

354
28133 31628 5619 8961 1003 9779 27591 14336 31618 17755 6349 17570 25604 24107 23136 21537 16494...

output:

1312
1 3
2 6
7 8
10 11
8 10
5 8
22 23
13 22
7 16
25 26
26 29
30 34
29 31
36 37
38 39
39 40
37 39
41 ...

result:

ok ok,using 6184 times

Test #8:

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

input:

512
14563 17808 18597 4341 12143 30490 13558 4331 30512 15302 14593 3642 21783 21775 23315 5766 1661...

output:

2039
3 4
2 3
6 8
3 7
9 10
10 12
15 16
13 15
12 13
6 12
17 18
19 20
18 19
19 22
29 31
28 29
21 28
10 ...

result:

ok ok,using 10122 times

Test #9:

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

input:

1000
1502 12015 26522 985 16804 3210 22284 28860 17265 9237 23503 15006 9625 30582 12808 25544 5298 ...

output:

4427
3 4
5 6
4 5
9 10
11 12
10 11
14 15
11 14
5 12
18 22
25 28
31 32
29 31
27 29
20 27
9 22
39 40
38...

result:

ok ok,using 24525 times

Test #10:

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

input:

1000
220 30195 7500 27597 28712 10097 25659 20392 16159 6016 31747 14902 5036 29017 31162 24365 2359...

output:

4481
2 3
5 6
3 5
11 12
12 13
4 12
17 18
19 20
18 19
21 24
19 22
25 26
26 29
21 26
8 22
43 44
41 43
4...

result:

ok ok,using 24499 times

Subtask #3:

score: 30
Accepted

Test #11:

score: 30
Accepted
time: 3ms
memory: 2288kb

input:

29160
3 3 5 5 4 4 5 1 3 2 5 1 4 3 2 3 1 2 1 5 4 4 4 0 2 3 4 2 1 4 4 5 3 3 5 4 2 4 4 1 3 5 1 1 2 2 2 ...

output:

38188
7 8
5 7
3 5
11 12
13 14
14 15
12 14
4 13
23 24
24 26
27 28
28 29
26 28
20 27
9 24
32 33
30 32
...

result:

ok ok,using 514564 times

Test #12:

score: 0
Accepted
time: 12ms
memory: 2296kb

input:

29654
4 0 1 1 0 2 2 3 2 4 2 3 0 1 2 1 1 0 2 2 5 2 5 4 4 5 0 2 3 4 2 5 1 1 0 2 2 2 2 5 3 5 2 1 0 1 5 ...

output:

38628
1 2
2 4
4 8
10 12
12 15
8 14
21 22
23 29
22 25
14 24
30 31
32 33
31 32
32 37
40 41
42 43
43 44...

result:

ok ok,using 522943 times

Test #13:

score: 0
Accepted
time: 9ms
memory: 1856kb

input:

23759
0 4 4 5 0 0 4 2 0 2 5 4 0 1 0 1 2 3 4 1 5 1 1 2 4 2 4 3 4 3 0 3 3 3 2 2 4 1 4 3 1 4 5 1 3 2 1 ...

output:

30993
4 5
5 6
2 5
7 8
8 9
9 10
4 9
19 20
20 24
7 22
25 26
29 30
26 29
28 36
37 38
38 41
43 44
44 45
...

result:

ok ok,using 408575 times

Test #14:

score: 0
Accepted
time: 14ms
memory: 2312kb

input:

32000
1 5 4 5 2 4 0 4 5 3 2 2 4 0 3 2 4 3 0 5 1 1 1 5 4 3 0 4 3 1 2 0 0 0 4 4 5 5 4 2 4 2 0 1 3 2 4 ...

output:

41179
6 7
2 6
9 10
10 12
13 14
14 16
12 15
4 14
17 18
18 19
19 23
25 26
26 27
27 32
22 30
10 27
39 4...

result:

ok ok,using 567288 times

Test #15:

score: 0
Accepted
time: 3ms
memory: 2316kb

input:

32000
2 5 2 0 0 2 5 2 0 0 1 2 0 5 3 4 0 1 5 2 3 4 5 3 1 5 1 4 5 2 5 0 1 4 0 1 3 0 5 2 2 2 2 5 0 1 1 ...

output:

41237
2 4
7 8
4 7
14 15
7 14
19 20
23 24
22 23
20 22
26 27
29 30
31 32
30 31
27 30
22 28
13 25
34 36...

result:

ok ok,using 567668 times

Subtask #4:

score: 10
Accepted

Test #16:

score: 10
Accepted
time: 21ms
memory: 5404kb

input:

25162
6548 134 11176 15393 24121 2053 29582 27616 22505 27930 3608 3082 22087 20841 5912 29959 21750...

output:

165559
5 6
8 12
6 9
14 15
17 18
15 17
20 22
23 25
21 23
16 21
8 17
26 27
27 30
36 38
35 36
28 35
39 ...

result:

ok ok,using 1307092 times

Test #17:

score: 0
Accepted
time: 15ms
memory: 3212kb

input:

13372
26001 8161 11243 31249 17641 3471 20342 11205 10364 6910 16562 14549 14518 1517 14171 739 2413...

output:

82532
1 2
2 3
5 6
3 5
11 14
4 13
17 18
18 20
22 24
23 27
20 25
10 23
28 29
30 31
29 30
32 33
30 32
3...

result:

ok ok,using 610381 times

Test #18:

score: 0
Accepted
time: 23ms
memory: 3264kb

input:

19761
26255 27109 5277 12037 28781 24950 6309 20913 27434 4457 25574 14446 10697 31185 14349 17737 2...

output:

127349
1 3
2 4
6 7
9 10
7 9
3 7
11 12
12 13
14 15
13 14
19 20
16 19
14 16
5 14
23 24
26 27
29 30
27 ...

result:

ok ok,using 979941 times

Test #19:

score: 0
Accepted
time: 30ms
memory: 5460kb

input:

32000
30347 31469 13058 20205 19829 2372 10241 20616 25222 30014 29774 414 1519 26519 882 14611 2885...

output:

214347
1 3
5 6
6 7
2 6
11 12
9 11
14 16
10 15
4 12
17 19
18 23
26 28
29 30
30 32
28 31
21 30
8 26
33...

result:

ok ok,using 1737836 times

Test #20:

score: 0
Accepted
time: 41ms
memory: 5460kb

input:

32000
29833 18417 7092 14816 30969 23083 28208 11380 24884 26793 6017 311 28930 24186 1060 13432 297...

output:

214149
1 4
7 8
5 7
3 5
9 12
13 16
11 14
4 12
17 18
18 19
21 22
23 24
22 23
19 22
28 31
21 30
8 26
34...

result:

ok ok,using 1736941 times