CSES - Datatähti 2017 alku - Results
Submission details
Task:Järjestys
Sender:Pohjantahti
Submission time:2016-10-13 17:06:33 +0300
Language:C++
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED19
#2ACCEPTED37
#3ACCEPTED44
Test results
testverdicttimegroup
#1ACCEPTED0.05 s1details
#2ACCEPTED0.06 s2details
#3ACCEPTED0.09 s3details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:67:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < res.size(); ++i) {
                                  ^
input/code.cpp:69:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i != res.size() - 1) cout << " ";
                               ^

Code

#include <iostream>
#include <vector>
#include <cmath>
// #include <fstream>
#include <algorithm>
using namespace std;
#define LSOne(S) (S & (-S))
typedef vector<int> vi;
typedef long long ll;
int n;
int pos[100005]; // ensimmäinen luku [1]
ll ft[100005]; // fenwick tree
vi res;
ll query(int b) {
ll sum = 0;
for (; b; b -= LSOne(b)) sum += ft[b];
return sum;
}
void update(int k, int v) {
for (; k <= n; k += LSOne(k)) ft[k] += v;
}
void swap(int src, int dest) {
if (src == dest) return;
if (src == 1) {
res.push_back(dest);
res.push_back(dest - 1);
}
else {
res.push_back(src);
res.push_back(dest);
res.push_back(dest - 1);
res.push_back(src - 1);
}
}
int main() {
ios_base::sync_with_stdio(0);
/*ifstream in("input.txt");
cin.rdbuf(in.rdbuf());*/
cin >> n;
for (int i = 1; i <= n; ++i) {
int cur;
cin >> cur;
pos[cur] = i;
//cout << "pos[" << cur << "] = " << i << endl;
}
for (int i = n; i > 0; --i) {
int src = pos[i] - query(pos[i]);
// cout << "Number " << i << " is at " << src << endl;
int dest = i;
if (i == src) continue;
// cout << "Swapping from " << src << " to " << dest << endl;
swap(src, dest);
update(pos[i] + 1, 1);
}
cout << res.size() << endl;
for (int i = 0; i < res.size(); ++i) {
cout << res[i];
if (i != res.size() - 1) cout << " ";
}
cout << endl;
return 0;
}

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
30
7 10 9 6 9 8 7 8 7 6 3 7 6 2 3...

Test 2

Group: 2

Verdict: ACCEPTED

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

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

user output
3972
6 1000 999 5 96 999 998 95 130...

Test 3

Group: 3

Verdict: ACCEPTED

input
100000
94703 47808 62366 31885 7091 8...

correct output
399956
98676 98676 98675 98676 62994 ...

user output
399932
35855 100000 99999 35854 3260 ...