CSES - Datatähti 2017 alku - Results
Submission details
Task:Järjestys
Sender:ollpu
Submission time:2016-10-16 00:57:40 +0300
Language:C++
Status:READY
Result:19
Feedback
groupverdictscore
#1ACCEPTED19
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.05 s1details
#20.06 s2details
#30.10 s3details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:35:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < movs.size(); ++i) {
                                 ^
input/code.cpp:43:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (fmovs.size() > 6*n) abort();
                        ^

Code

#include <iostream>
#include <vector>
using namespace std;
vector<int> movs, fmovs;
void reverse(int a, int b) {
  movs.push_back(b);
  if (a != 0) {
    movs.push_back(b-a);
    movs.push_back(b);
  }
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  int t[n], d[n];
  for (int i = 0; i < n; ++i) {
    int k;
    cin >> k;
    t[i] = --k;
    d[k] = i;
  }
  for (int i = 0; i < n; ++i) {
    if (d[i] == i) continue;
    int a = min(d[i], i), b = max(d[i], i);
    reverse(a, b);
    if (b-a >= 3) reverse(a+1, b-1);
    int tmp = d[i];
    d[t[i]] = tmp;
    d[i] = i;
    swap(t[i], t[tmp]);
  }
  for (int i = 0; i < movs.size(); ++i) {
    if (!fmovs.empty() && fmovs.back() == movs[i]) {
      fmovs.pop_back();
    } else {
      fmovs.push_back(movs[i]);
    }
  }
  cout << fmovs.size() << endl;
  if (fmovs.size() > 6*n) abort();
  for (int mov : fmovs) {
    cout << mov+1 << ' ';
  }
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
10
9 3 4 7 6 5 10 2 8 1

correct output
32
10 10 9 10 9 8 7 9 4 2 1 4 5 2...

user output
34
10 9 8 9 8 7 8 7 5 7 8 6 8 7 4...

Test 2

Group: 2

Verdict:

input
1000
650 716 982 41 133 1000 876 92...

correct output
3984
207 207 206 207 128 127 126 12...

user output
5880
207 206 205 206 127 126 127 12...

Test 3

Group: 3

Verdict:

input
100000
94703 47808 62366 31885 7091 8...

correct output
399956
98676 98676 98675 98676 62994 ...

user output
599818
98676 98675 98674 98675 62993 ...