ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#214239 | #2022. a | nullptr_qwq | 100 | 171ms | 5460kb | C++11 | 5.8kb | 2024-11-16 19:27:39 | 2024-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