| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 26615 |
2017-07-03T12:52:22 Z |
model_code |
Shift (POI11_prz) |
C++11 |
|
243 ms |
8996 KB |
/*************************************************************************
* *
* XVIII Olimpiada Informatyczna *
* *
* Zadanie: Przekladanka *
* Autor: Miroslaw Michalski *
* Zlozonosc czasowa: O(n^2) *
* Opis: Rozwiazanie alternatywne *
* *
*************************************************************************/
#include <cstdio>
const char* invalid = "NIE DA SIE";
struct Circle {
Circle(int* x, int n)
: n_(n)
, begin_(0)
, lastPosition_(0)
, ansPosition_(0) {
x_ = new int[n_];
ans_ = new short[n_ * n_];
for(int i=0; i<n_; i++) x_[i] = x[i];
}
~Circle() {
delete[] x_;
delete[] ans_;
}
void move(int from, int dest);
bool sort();
int distance(int from, int dest);
int distance2(int from, int dest) {
return distance(dest, from);
}
void performPlus(int x);
void performMinus(int x);
int* x_;
short* ans_;
int n_;
int begin_;
int lastPosition_;
int ansPosition_;
};
int Circle::distance(int from, int dest) {
int dist = from - dest;
if (dist < 0) {
dist += n_;
}
return dist;
}
void Circle::performPlus(int x) {
if (x == 0 || x == n_) return ;
begin_ -= x;
if (begin_ < 0) begin_ += n_;
ans_[ansPosition_++] = x;
}
void Circle::performMinus(int x) {
int fi = begin_;
int se = (begin_ + 1) % n_;
int th = (begin_ + 2) % n_;
int x_fi = x_[fi];
int x_se = x_[se];
int x_th = x_[th];
if (x == 1) {
x_[fi] = x_th;
x_[se] = x_fi;
x_[th] = x_se;
} else {
x_[fi] = x_se;
x_[se] = x_th;
x_[th] = x_fi;
}
ans_[ansPosition_++] = (-1) * x;
}
void Circle::move(int from, int dest) {
int dist = distance(from, dest);
if (dist == 0) return ;
int newPos = from;
while (dist >= 2) {
newPos -= 2;
if (newPos < 0) newPos += n_;
performPlus(distance2(newPos, begin_));
performMinus(1);
dist -= 2;
}
if (dist == 1) {
newPos = dest;
performPlus(distance2(newPos, begin_));
performMinus(2);
}
}
bool Circle::sort() {
// finding '1' in our set
for(int i=0; i<n_; i++) if (x_[i] == 1) {
lastPosition_ = i;
break;
}
int from = -1, dest = (lastPosition_ + 1) % n_;
for(int i=2; i<=n_-2; i++) {
for(int j=0; j<n_; j++) {
if (x_[j] == i) {
from = j;
break;
}
}
move(from, dest);
dest = (dest + 1) % n_;
}
if (x_[(dest + 1) % n_] != n_) {
if (n_ % 2) return false;
performPlus(distance2(dest, begin_));
performMinus(2);
for(int i=0; i<n_/2 - 1; i++) {
performPlus(n_ - 2);
performMinus(2);
}
}
for(int i = 0; i < n_; i++) if (x_[i] == 1) {
performPlus(distance2(i, begin_));
break;
}
return true;
}
const int MAXN = 2013;
int main() {
int n;
int a[MAXN];
scanf("%d",&n);
for(int i=0; i<n; i++) {
scanf("%d",&a[i]);
}
if (n == 2) {
if (a[0] == 1) printf("0\n"); else printf("1\n1a\n");
return 0;
}
Circle cir(a, n);
if (cir.sort()) {
printf("%u\n",cir.ansPosition_);
for(int i=0; i<cir.ansPosition_; i++) {
int x = cir.ans_[i];
if (x > 0) {
printf("%da ",x);
} else {
printf("%db ",x * (-1));
}
}
} else {
printf("%s",invalid);
}
return 0;
}
Compilation message
prz.cpp: In function 'int main()':
prz.cpp:155:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
prz.cpp:157:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&a[i]);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1180 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1180 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1180 KB |
Output is correct |
| 4 |
Correct |
0 ms |
1180 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1180 KB |
Output is correct |
| 6 |
Correct |
0 ms |
1180 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1180 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1180 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1180 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1180 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1180 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1180 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1336 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1336 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
1672 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1668 KB |
Output is correct |
| 3 |
Correct |
6 ms |
1668 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
69 ms |
6184 KB |
Output is correct |
| 2 |
Correct |
59 ms |
6176 KB |
Output is correct |
| 3 |
Correct |
56 ms |
6168 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
99 ms |
7512 KB |
Output is correct |
| 2 |
Correct |
89 ms |
7504 KB |
Output is correct |
| 3 |
Correct |
76 ms |
7496 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
126 ms |
8996 KB |
Output is correct |
| 2 |
Correct |
119 ms |
8988 KB |
Output is correct |
| 3 |
Correct |
243 ms |
8996 KB |
Output is correct |
| 4 |
Correct |
0 ms |
8908 KB |
Output is correct |
| 5 |
Correct |
9 ms |
8988 KB |
Output is correct |
