Task: | Järjestys |
Sender: | Binäärihau |
Submission time: | 2016-10-03 00:40:28 +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.05 s | 2 | details |
#3 | ACCEPTED | 0.13 s | 3 | details |
Code
#include <bits/stdc++.h> #define uint unsigned int #define ull unsigned long long #define INF 1000000001 #define LINF 1000000000000000001 #define ll long long #define ld long double #define M 1000000007 #define E 0.0000001 #define N (1<<17) #define pii pair<int, int> #define pll pair<long long, long long> #define pdd pair<double, double> #define pld pair<long double, long double> #define cll complex<long long> #define cld complex<long double> #define X real() #define Y imag() #define C 'a' #define F first #define S second #define PI 3.1415926535897932384626433 using namespace std; int v[2*N]; void inc (int k) { k += N; v[k]++; for (k /= 2; k >= 1; k /= 2) v[k] = v[2 * k] + v[2 * k + 1]; } int sum (int k) { int a = 1; int b = k; a += N; b += N; int s = 0; while (a <= b) { if (a % 2 == 1) s += v[a++]; if (b % 2 == 0) s += v[b--]; a /= 2; b /= 2; } return s; } int p[N]; int main () { int n; cin>>n; for (int i = 1; i <= n; i++) { int x; cin>>x; p[x] = i; } vector<int> ans; for (int i = n; i > 1; i--) { int x = p[i] - sum(p[i]); //cout<<i<<" -> "<<x<<endl; inc(p[i]); if (x != 1) ans.push_back(x - 1); if (x != 1) ans.push_back(x); ans.push_back(i); ans.push_back(i - 1); } cout<<ans.size()<<endl; for (int i : ans) cout<<i<<" "; cout<<endl; }
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 6 7 10 9 9 8 6 7 8 7 2 3 7 6 2... |
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 |
---|
3988 5 6 1000 999 95 96 999 998 129... |
Test 3
Group: 3
Verdict: ACCEPTED
input |
---|
100000 94703 47808 62366 31885 7091 8... |
correct output |
---|
399956 98676 98676 98675 98676 62994 ... |
user output |
---|
399964 35854 35855 100000 99999 3259 ... |