oj.uz

Submission #29571

# Submission time Handle Problem Language Result Execution time Memory
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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2028 KB Output is correct
2 Correct 0 ms 2028 KB Output is correct
3 Correct 0 ms 2028 KB Output is correct
4 Correct 0 ms 2028 KB Output is correct
5 Correct 0 ms 2028 KB Output is correct
6 Correct 0 ms 2028 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2028 KB Output is correct
2 Correct 0 ms 2028 KB Output is correct
3 Correct 0 ms 2028 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2168 KB Output is correct
2 Correct 0 ms 2028 KB Output is correct
3 Correct 0 ms 2168 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2300 KB Output is correct
2 Correct 0 ms 2300 KB Output is correct
3 Correct 0 ms 2300 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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