# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1025107 | 2024-07-16T16:04:19 Z | nvujica | Gondola (IOI14_gondola) | C++14 | 19 ms | 2776 KB |
#include <bits/stdc++.h> #include "gondola.h" #define ll long long #define fi first #define se second using namespace std; const int maxn = 3e5 + 10, mod = 1e9 + 9, LOG = 30; int a[maxn]; int bio[maxn]; vector <pair<int, int> > v; int pot[LOG]; int mul(int x, int y){ return ((ll)x * y) % mod; } int valid(int n, int inputSeq[]){ for(int i = 0; i < n; i++){ a[i] = inputSeq[i] - 1; if(bio[a[i]]) return 0; bio[a[i]] = 1; } for(int i = 0; i < n; i++){ if(a[i] < n){ for(int j = 0; j < n; j++){ if(a[(i + j) % n] < n){ if(a[(i + j) % n] != (a[i] + j) % n) return 0; } } break; } } return 1; } int replacement(int n, int gondolaSeq[], int replacementSeq[]){ for(int i = 0; i < n; i++){ a[i] = gondolaSeq[i]; } for(int i = 0; i < n; i++){ if(a[i] > n) v.push_back({a[i], i}); } for(int i = n - 1; i >= 0; i--){ if(a[i] <= n || !i){ for(int j = 0; j < n; j++){ a[(i + j) % n] = (a[i] - 1 + j) % n + 1; } break; } } // cout << v.size() << endl; sort(v.begin(), v.end()); int p = 0, l = 0; while(p < v.size()){ replacementSeq[l] = a[v[p].se]; // cout << a[v[p].se] << ' '; a[v[p].se] = n + l + 1; l++; if(a[v[p].se] == v[p].fi) p++; } // cout << endl; // cout << l; return l; } int calc(int x, int p){ pot[0] = x; for(int i = 1; i < LOG; i++){ pot[i] = mul(pot[i - 1], pot[i - 1]); } int ret = 1; for(int i = 0; i < LOG; i++){ if(p & (1 << i)) ret = mul(ret, pot[i]); } return ret; } int countReplacement(int n, int inputSeq[]){ if(!valid(n, inputSeq)) return 0; for(int i = 0; i < n; i++){ a[i] = inputSeq[i]; } for(int i = 0; i < n; i++){ if(a[i] > n) v.push_back({a[i], i}); } // for(int i = n - 1; i >= 0; i--){ // if(a[i] <= n || !i){ // for(int j = 0; j < n; j++){ // a[(i + j) % n] = (a[i] - 1 + j) % n + 1; // } // break; // } // } // cout << v.size() << endl; // cout << v.size() << endl; // if(v.size() == 0) return 1; sort(v.begin(), v.end()); // for(int i = 0; i < v.size(); i++){ // cout << v[i].fi << ' ' << v[i].se << endl; // } int p = 0, l = n, ans = 1; // while(p < v.size()){ // l++; // if(a[v[p].se] == l){ // p++; // continue; // } // ans = mul(ans, v.size() - p); // } int zad = n; for(int i = 0; i < v.size(); i++){ // cout << v[i].fi << ' ' << zad << ": "; // cout << v.size() - i << ' ' << v[i].fi - zad - 1 << endl; ans = mul(ans, calc(v.size() - i, v[i].fi - zad - 1)); zad = v[i].fi; } // cout << endl; // cout << l; if(v.size() == n) ans = mul(ans, n); return ans; } //int main(){ // ios_base::sync_with_stdio(0); // cin.tie(0); // // int n; // cin >> n; // int inputSeq[n]; // for(int i = 0; i < n; i++){ // cin >> inputSeq[i]; // } // cout << countReplacement(n, inputSeq); // // return 0; //}
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Correct | 1 ms | 344 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 1 ms | 348 KB | Output is correct |
6 | Correct | 4 ms | 964 KB | Output is correct |
7 | Correct | 6 ms | 1472 KB | Output is correct |
8 | Correct | 6 ms | 1628 KB | Output is correct |
9 | Correct | 2 ms | 604 KB | Output is correct |
10 | Correct | 7 ms | 1908 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 1 ms | 344 KB | Output is correct |
4 | Correct | 1 ms | 344 KB | Output is correct |
5 | Correct | 0 ms | 344 KB | Output is correct |
6 | Correct | 3 ms | 860 KB | Output is correct |
7 | Correct | 6 ms | 1372 KB | Output is correct |
8 | Correct | 6 ms | 1624 KB | Output is correct |
9 | Correct | 2 ms | 604 KB | Output is correct |
10 | Correct | 7 ms | 1880 KB | Output is correct |
11 | Correct | 0 ms | 348 KB | Output is correct |
12 | Correct | 0 ms | 348 KB | Output is correct |
13 | Correct | 3 ms | 1628 KB | Output is correct |
14 | Correct | 1 ms | 348 KB | Output is correct |
15 | Correct | 7 ms | 1952 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 444 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 1 ms | 344 KB | Output is correct |
5 | Correct | 0 ms | 344 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 1 ms | 348 KB | Output is correct |
8 | Correct | 0 ms | 348 KB | Output is correct |
9 | Correct | 1 ms | 348 KB | Output is correct |
10 | Correct | 1 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 440 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 1 ms | 348 KB | Output is correct |
5 | Correct | 1 ms | 348 KB | Output is correct |
6 | Correct | 1 ms | 348 KB | Output is correct |
7 | Correct | 1 ms | 344 KB | Output is correct |
8 | Correct | 1 ms | 348 KB | Output is correct |
9 | Correct | 1 ms | 348 KB | Output is correct |
10 | Correct | 1 ms | 348 KB | Output is correct |
11 | Correct | 6 ms | 1396 KB | Output is correct |
12 | Correct | 6 ms | 1596 KB | Output is correct |
13 | Correct | 10 ms | 2004 KB | Output is correct |
14 | Correct | 6 ms | 1448 KB | Output is correct |
15 | Correct | 12 ms | 2516 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 344 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 1 ms | 348 KB | Output is correct |
4 | Correct | 1 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 1 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Correct | 0 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 360 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 1 ms | 344 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Correct | 0 ms | 348 KB | Output is correct |
9 | Correct | 19 ms | 2740 KB | Output is correct |
10 | Correct | 15 ms | 2264 KB | Output is correct |
11 | Correct | 9 ms | 1628 KB | Output is correct |
12 | Correct | 8 ms | 1628 KB | Output is correct |
13 | Correct | 2 ms | 860 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 444 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Correct | 0 ms | 348 KB | Output is correct |
9 | Correct | 19 ms | 2776 KB | Output is correct |
10 | Correct | 15 ms | 2492 KB | Output is correct |
11 | Correct | 7 ms | 1628 KB | Output is correct |
12 | Correct | 10 ms | 1628 KB | Output is correct |
13 | Correct | 3 ms | 812 KB | Output is correct |
14 | Runtime error | 9 ms | 1884 KB | Execution killed with signal 11 |
15 | Halted | 0 ms | 0 KB | - |