oj.uz

답안 #378378

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
378378 2021-03-16T15:29:57 Z kshitij_sodani Shift (POI11_prz) C++14
0 / 100
 167 ms 30908 KB 
//#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<<"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;
		}
		if(j.a==0){
			cout<<"a";
		}
		else{
			cout<<"b";
		}
		cout<<j.b<<" ";
	}
	cout<<endl;




 
	return 0;
}

Compilation message

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

Subtask #1
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Failed 1 ms 364 KB Wrong format
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Failed 1 ms 364 KB Wrong format
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Failed 1 ms 492 KB Wrong format
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Failed 2 ms 768 KB Wrong format
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Failed 11 ms 2280 KB Wrong format
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Failed 116 ms 20304 KB Wrong format
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Failed 144 ms 27036 KB Wrong format
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Failed 167 ms 30908 KB Wrong format
2 Halted 0 ms 0 KB -