Submission #378381

#	Time	Username	Problem	Language	Result	Execution time	Memory
378381		kshitij_sodani	Shift (POI11_prz)	C++14	100 / 100	252 ms	61976 KiB

prz

//#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 (stderr)

prz.cpp: In function 'int main()':
prz.cpp:54:7: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |   int ind;
      |       ^~~

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 13 / 13
• Subtask 8: 13 / 13