//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#define endl '\n'
llo n;
llo it[2001];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n;
for(llo i=0;i<n;i++){
cin>>it[i];
it[i]--;
}
llo co=0;
for(llo i=0;i<n;i++){
for(llo j=i+1;j<n;j++){
if(it[i]>it[j]){
co++;
}
}
}
if(co%2==1 and n%2==1){
cout<<"NIE DA SIE"<<endl;
return 0;
}
if(n==1){
cout<<0<<endl;
return 0;
}
if(n==2){
if(it[0]==0){
cout<<0<<endl;
}
else{
cout<<1<<endl;
cout<<"1a"<<endl;
}
return 0;
}
vector<pair<int,int>> ans;
for(int i=0;i<n-2;i++){
if(it[i]==i){
continue;
}
int ind;
for(int j=0;j<n;j++){
if(it[j]==i){
ind=j;
}
}
//cout<<ind<<":"<<endl;
while(ind>i+1){
if(ind-2>0){
ans.pb({0,n-(ind-2)});
}
ans.pb({1,1});
if(ind-2>0){
ans.pb({0,ind-2});
}
int x=it[ind-2];
int y=it[ind-1];
int z=it[ind];
it[ind-2]=z;
it[ind-1]=x;
it[ind]=y;
ind-=2;
}
if(ind==i+1){
if(ind-1>0){
ans.pb({0,n-(ind-1)});
}
ans.pb({1,2});
if(ind-1>0){
ans.pb({0,(ind-1)});
}
int x=it[ind-1];
int y=it[ind];
int z=it[ind+1];
it[ind-1]=y;
it[ind]=z;
it[ind+1]=x;
}
}
if(it[n-2]==n-1){
int ind=n-1;
while(ind!=n-3){
//st=1;
if(n-ind<n){
ans.pb({0,n-ind});
}
ans.pb({1,2});
int x=it[ind];
int y=it[(ind+1)%n];
int z=it[(ind+2)%n];
it[(ind+2)%n]=x;
it[(ind+1)%n]=z;
it[ind]=y;
if(n-ind<n){
ans.pb({0,ind});
}
ind=(ind+2)%n;
}
ans.pb({0,1});
}
vector<pair<int,int>> ans2;
for(auto j:ans){
if(ans2.size()==0){
ans2.pb(j);
continue;
}
if(ans2.back().a==j.a){
ans2[ans2.size()-1].b+=j.b;
ans2[ans2.size()-1].b%=n;
if(ans2.back().b==0){
ans2.pop_back();
}
}
else{
ans2.pb(j);
}
}
/*int coo=0;
for(auto j:ans2){
if(j.b!=n){
coo++;
}
}*/
cout<<ans2.size()<<endl;
for(auto j:ans2){
if(j.b==n){
continue;
}
cout<<j.b;
if(j.a==0){
cout<<"a ";
}
else{
cout<<"b ";
}
}
cout<<endl;
return 0;
}
Compilation message
prz.cpp: In function 'int main()':
prz.cpp:54:7: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
54 | int ind;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
0 ms |
364 KB |
Output is correct |
| 5 |
Correct |
0 ms |
364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
0 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
748 KB |
Output is correct |
| 2 |
Correct |
2 ms |
748 KB |
Output is correct |
| 3 |
Correct |
2 ms |
748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
2280 KB |
Output is correct |
| 2 |
Correct |
8 ms |
2280 KB |
Output is correct |
| 3 |
Correct |
10 ms |
2280 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
83 ms |
20312 KB |
Output is correct |
| 2 |
Correct |
87 ms |
20316 KB |
Output is correct |
| 3 |
Correct |
83 ms |
20188 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
109 ms |
26940 KB |
Output is correct |
| 2 |
Correct |
115 ms |
27196 KB |
Output is correct |
| 3 |
Correct |
110 ms |
26556 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
126 ms |
30888 KB |
Output is correct |
| 2 |
Correct |
127 ms |
31164 KB |
Output is correct |
| 3 |
Correct |
252 ms |
61976 KB |
Output is correct |
| 4 |
Correct |
7 ms |
364 KB |
Output is correct |
| 5 |
Correct |
2 ms |
364 KB |
Output is correct |
