Submission #1131289
Source Code Expand
#include <stdio.h> #include <iostream> #include <cstring> #include <vector> #include <algorithm> #include <cstdlib> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #include <ctime> #include <cassert> #include <unordered_map> #include <fstream> #include <random> #include <cstring> #include <complex> #include <bitset> #define all(a) (a).begin(), (a).end() #define sz(a) (int)(a).size() #define pb push_back using namespace std; const int P = 1e9 + 7; typedef long long ll; typedef long double ld; mt19937 rr(random_device{}()); vector<int> f; int n; void update(int pos, int val) { for (int i = pos; i < n; i = i | (i + 1)) f[i] += val; } int sum(int pos) { int ans = 0; for (int i = pos; i >= 0; i = (i & (i + 1)) - 1) ans += f[i]; return ans; } int main() { // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); ios_base::sync_with_stdio(false); cin.tie(0); cin >> n; vector<int> x(n); for (int i = 0; i < n; ++i) cin >> x[i]; int m = 0; vector<int> p; vector<int> used(n); for (int i = 0; i < n; ++i) { ++m; if (m > (x[i] + 1) / 2) { --m; used[i] = 1; p.push_back(i); } } for (int i = n - 1; i >= 0; --i) { if (!used[i]) p.push_back(i); } f.resize(n); for (int i = 0; i < n; ++i) update(i, 1); vector<ll> fact(n); fact[0] = 1; for (ll i = 1; i < n; ++i) { fact[i] = fact[i - 1] * i % P; } ll ans = 1; for (int i = 0; i < n; ++i) { ll x = sum(p[i]); ans += fact[n - i - 1] * (x - 1); ans %= P; update(p[i], -1); } cout << ans << endl; }
Submission Info
Submission Time | |
---|---|
Task | A - Robot Racing |
User | AndreySergunin |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1672 Byte |
Status | WA |
Exec Time | 16 ms |
Memory | 2808 KB |
Judge Result
Set Name | Sample | Subtask | All | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 500 | 0 / 400 | ||||||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt |
Subtask | 0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt |
All | 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 2_00.txt, 2_01.txt, 2_02.txt, 2_03.txt, 2_04.txt, 2_05.txt, 2_06.txt, 2_07.txt, 2_08.txt, 2_09.txt, 2_10.txt, 2_11.txt, 2_12.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
0_00.txt | AC | 1 ms | 256 KB |
0_01.txt | AC | 1 ms | 256 KB |
0_02.txt | AC | 1 ms | 256 KB |
0_03.txt | AC | 1 ms | 256 KB |
1_00.txt | AC | 1 ms | 256 KB |
1_01.txt | AC | 1 ms | 256 KB |
1_02.txt | AC | 1 ms | 256 KB |
1_03.txt | WA | 1 ms | 256 KB |
1_04.txt | AC | 1 ms | 256 KB |
1_05.txt | AC | 1 ms | 256 KB |
1_06.txt | WA | 1 ms | 256 KB |
1_07.txt | AC | 1 ms | 256 KB |
1_08.txt | AC | 1 ms | 256 KB |
1_09.txt | AC | 1 ms | 256 KB |
1_10.txt | AC | 1 ms | 256 KB |
2_00.txt | WA | 14 ms | 2808 KB |
2_01.txt | AC | 14 ms | 2808 KB |
2_02.txt | AC | 16 ms | 2808 KB |
2_03.txt | WA | 15 ms | 2808 KB |
2_04.txt | WA | 15 ms | 2680 KB |
2_05.txt | WA | 15 ms | 2808 KB |
2_06.txt | WA | 14 ms | 2680 KB |
2_07.txt | WA | 14 ms | 2808 KB |
2_08.txt | WA | 14 ms | 2680 KB |
2_09.txt | WA | 14 ms | 2680 KB |
2_10.txt | WA | 14 ms | 2680 KB |
2_11.txt | AC | 16 ms | 2680 KB |
2_12.txt | AC | 16 ms | 2680 KB |