Task: | Järjestys |
Sender: | Pohjantahti |
Submission time: | 2016-10-13 17:06:33 +0300 |
Language: | C++ |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 19 |
#2 | ACCEPTED | 37 |
#3 | ACCEPTED | 44 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.05 s | 1 | details |
#2 | ACCEPTED | 0.06 s | 2 | details |
#3 | ACCEPTED | 0.09 s | 3 | details |
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 treevi 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 ... |