답안 #29571 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
29571	2017-07-20T06:48:15 Z	시제연(#1241)	Shift (POI11_prz)	C++11	100 / 100	303 ms	26688 KB

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;
int n;
int arr[2100];
vector<pii> ord;

int inv() {
	int i, j, cnt = 0;
	for (i=0;i<n;i++) {
		for (j=i+1;j<n;j++) if(arr[i]>arr[j]) cnt++;
	}
	return cnt;
}
void push(pii a) {
	if (!ord.empty()&&ord.back().second==a.second) ord.back().first += a.first;
	else ord.push_back(a);
	if (ord.back().second&&ord.back().first%3==0) ord.pop_back();
	else if (ord.back().second==0&&ord.back().first%n==0) ord.pop_back();
}
void chan(int &cur, int now) {
	push(pii((cur+n-now)%n,0));
	cur = now;
}
void fly(int &cur) {
	push(pii(1,1));
	int tmp = arr[cur+2];
	arr[cur+2] = arr[cur+1];
	arr[cur+1] = arr[cur];
	arr[cur] = tmp;
}
void solve() {
	int tar, cur = 0;
	for (tar=1;tar<=n-2;tar++) {
		int loc;
		for (loc=0;loc<n;loc++) if (arr[loc]==tar) break;
		while(loc>=1+tar) {
			chan(cur,loc-2);
			fly(cur);
			loc -= 2;
		}
		if (loc==tar) {
			chan(cur,tar-1);
			fly(cur); fly(cur);
		}
	}
	chan(cur,0);
}

void print() {
	int i;
	printf("%d\n",ord.size());
	for (i=0;i<ord.size();i++) {
		printf("%d%c ",ord[i].first,ord[i].second+'a');
	}
	printf("\n");
}

int main() {
	int i;

	scanf("%d",&n);
	for (i=0;i<n;i++) scanf("%d",&arr[i]);
	int t = inv();
	if (n%2==1&&t%2==1) {
		printf("NIE DA SIE\n");
		return 0;
	}
	if (t%2==1) {
		int tmp = arr[n-1];
		for (i=n-1;i>0;i--) arr[i] = arr[i-1];
		arr[0] = tmp;
		push(pii(1,0));
	}
	solve();
	print();

    return 0;
}

Compilation message

prz.cpp: In function 'void print()':
prz.cpp:54:26: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<std::pair<int, int> >::size_type {aka long unsigned int}' [-Wformat=]
  printf("%d\n",ord.size());
                          ^
prz.cpp:55:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i=0;i<ord.size();i++) {
            ^
prz.cpp: In function 'int main()':
prz.cpp:64:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
prz.cpp:65:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (i=0;i<n;i++) scanf("%d",&arr[i]);
                                       ^

Subtask #1
12.0 / 12.0

#	결과	메모리	Grader output
1	Correct	2028 KB	Output is correct
2	Correct	2028 KB	Output is correct
3	Correct	2028 KB	Output is correct
4	Correct	2028 KB	Output is correct
5	Correct	2028 KB	Output is correct
6	Correct	2028 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	메모리	Grader output
1	Correct	2028 KB	Output is correct
2	Correct	2028 KB	Output is correct
3	Correct	2028 KB	Output is correct

Subtask #3
12.0 / 12.0

#	결과	메모리	Grader output
1	Correct	2168 KB	Output is correct
2	Correct	2028 KB	Output is correct
3	Correct	2168 KB	Output is correct

Subtask #4
12.0 / 12.0

#	결과	메모리	Grader output
1	Correct	2300 KB	Output is correct
2	Correct	2300 KB	Output is correct
3	Correct	2300 KB	Output is correct

Subtask #5
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	2880 KB	Output is correct
2	Correct	9 ms	2880 KB	Output is correct
3	Correct	6 ms	2880 KB	Output is correct

Subtask #6
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	73 ms	14400 KB	Output is correct
2	Correct	86 ms	14400 KB	Output is correct
3	Correct	109 ms	14400 KB	Output is correct

Subtask #7
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	116 ms	14400 KB	Output is correct
2	Correct	139 ms	14400 KB	Output is correct
3	Correct	116 ms	14400 KB	Output is correct

Subtask #8
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	139 ms	14400 KB	Output is correct
2	Correct	123 ms	14400 KB	Output is correct
3	Correct	303 ms	26688 KB	Output is correct
4	Correct	3 ms	2028 KB	Output is correct
5	Correct	0 ms	2028 KB	Output is correct