# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
389346 | 2021-04-14T03:28:51 Z | abc864197532 | Permutation Recovery (info1cup17_permutation) | C++17 | 4000 ms | 69896 KB |
#include <bits/stdc++.h> using namespace std; #define lli long long int #define pb push_back #define eb emplace_back #define mp make_pair #define test(x) cout << #x << ' ' << x << endl #define printv(x) { \ for (auto a : x) cout << a << ' '; \ cout << endl; \ } #define pii pair<int, int> #define pll pair<lli, lli> #define X first #define Y second #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() const int N = 512, abc = 864197532; struct BigInt { vector <int> val; BigInt(string s = "0") { for (int i = s.length() - 1; ~i; --i) { val.pb(s[i] - '0'); } } BigInt operator - (const BigInt &o) const { vector <int> a = val; vector <int> result(a.size()); for (int i = 0; i < o.val.size(); ++i) { if (a[i] >= o.val[i]) result[i] = a[i] - o.val[i]; else result[i] = a[i] - o.val[i] + 10, a[i + 1]--; } for (int i = o.val.size(); i < a.size(); ++i) { result[i] = a[i]; } while (result.size() > 1 && result.back() == 0) result.pop_back(); BigInt ans; ans.val.pop_back(); for (int i : result) ans.val.pb(i); return ans; } bool operator == (const BigInt &o) const { return val == o.val; } }; int main () { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector <BigInt> a; string s; for (int i = 0; i < n; ++i) cin >> s, a.pb(BigInt(s)); vector <BigInt> d(n); vector <int> p(n, 0); int now = 1; for (int i = 0; i < n; ++i) { d[i] = (i ? a[i] - a[i - 1] : a[i]); } vector <BigInt> cur = d; while (now <= n) { int i; for (i = n - 1; ~i; --i) { if (!p[i] && cur[i] == BigInt("1")) break; } p[i] = now++; for (int j = i + 1; j < n; ++j) if (!p[j]) { cur[j] = cur[j] - d[i]; } } printv(p); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
2 | Correct | 16 ms | 332 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
2 | Correct | 16 ms | 332 KB | Output is correct |
3 | Correct | 162 ms | 1184 KB | Output is correct |
4 | Correct | 225 ms | 1124 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
2 | Correct | 16 ms | 332 KB | Output is correct |
3 | Correct | 162 ms | 1184 KB | Output is correct |
4 | Correct | 225 ms | 1124 KB | Output is correct |
5 | Execution timed out | 4065 ms | 69896 KB | Time limit exceeded |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
2 | Correct | 16 ms | 332 KB | Output is correct |
3 | Correct | 162 ms | 1184 KB | Output is correct |
4 | Correct | 225 ms | 1124 KB | Output is correct |
5 | Execution timed out | 4065 ms | 69896 KB | Time limit exceeded |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
2 | Correct | 16 ms | 332 KB | Output is correct |
3 | Correct | 162 ms | 1184 KB | Output is correct |
4 | Correct | 225 ms | 1124 KB | Output is correct |
5 | Execution timed out | 4065 ms | 69896 KB | Time limit exceeded |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
2 | Correct | 16 ms | 332 KB | Output is correct |
3 | Correct | 162 ms | 1184 KB | Output is correct |
4 | Correct | 225 ms | 1124 KB | Output is correct |
5 | Execution timed out | 4065 ms | 69896 KB | Time limit exceeded |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
2 | Correct | 16 ms | 332 KB | Output is correct |
3 | Correct | 162 ms | 1184 KB | Output is correct |
4 | Correct | 225 ms | 1124 KB | Output is correct |
5 | Execution timed out | 4065 ms | 69896 KB | Time limit exceeded |