# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1042901 | 2024-08-03T14:24:54 Z | dpsaveslives | Gondola (IOI14_gondola) | C++17 | 22 ms | 5212 KB |
#include "gondola.h" #include <bits/stdc++.h> #define f first #define s second #define ll long long using namespace std; const int MAXN = 1e5; const int MOD = 1e9+9; ll fac[MAXN+1]; ll exp(ll x, ll n){ x %= MOD; ll res = 1; while(n > 0){ if(n % 2 == 1){ res = res*x%MOD; } x = x*x%MOD; n /= 2; } return res; } void factorial(){ fac[0] = 1; for(int i = 1;i<=MAXN;++i){ fac[i] = fac[i-1]*i%MOD; } } int valid(int n, int inputSeq[]){ int pos = -1; set<int> vals; for(int i = 0;i<n;++i){ if(inputSeq[i] <= n && pos == -1){ pos = i; } vals.insert(inputSeq[i]); } if(vals.size() != n){ return 0; } if(pos == -1){ return 1; } int cur = inputSeq[pos]; for(int i = pos;i<n;++i){ if(inputSeq[i] <= n){ //cout << i << " " << cur << "\n"; if(inputSeq[i] != cur){ return 0; } } if(cur == n){ cur = 0; } ++cur; } for(int i = 0;i<=pos-1;++i){ if(inputSeq[i] <= n){ if(inputSeq[i] != cur){ return 0; } } if(cur == n){ cur = 0; } ++cur; } return 1; } int replacement(int n, int gondolaSeq[], int replacementSeq[]){ vector<pair<int,int>> arr; int pos = -1; bool any = false; for(int i = 0;i<n;++i){ if(gondolaSeq[i] <= n){ if(pos == -1){ pos = i; } } else{ any = true; arr.push_back({gondolaSeq[i],i}); } } if(!any){ return 0; } int rep = 0, cur; if(pos != -1){ cur = gondolaSeq[pos]; } else{ cur = 1; pos = 0; } vector<int> reps(n,-1); for(int i = pos;i<n;++i){ if(gondolaSeq[i] > n){ reps[i] = cur; } if(cur == n){ cur = 0; } ++cur; } for(int i = 0;i<=pos-1;++i){ if(gondolaSeq[i] > n){ reps[i] = cur; } if(cur == n){ cur = 0; } ++cur; } sort(arr.begin(),arr.end()); cur = n+1; int i = 0; while(i < arr.size()){ replacementSeq[rep] = reps[arr[i].s]; //cout << rep << " " << replacementSeq[rep] << "\n"; ++rep; while(cur < arr[i].f){ //until arr[i] = cur replacementSeq[rep] = cur; //cout << rep << " " << replacementSeq[rep] << "\n"; ++rep; ++cur; } ++cur; ++i; } return rep; } int countReplacement(int n, int inputSeq[]){ if(!valid(n,inputSeq)) return 0; int pos = -1; bool any = false; vector<pair<int,int>> arr; for(int i = 0;i<n;++i){ if(inputSeq[i] <= n){ if(pos == -1){ pos = i; } } else{ any = true; arr.push_back({inputSeq[i],i}); } } if(!any){ return 1; } ll ans = 1ll; if(pos == -1){ //no value that is <= n factorial(); ans = fac[n]%MOD; } sort(arr.begin(),arr.end()); int cur = n+1; int i = 0; ll cnt = arr.size(); while(i < arr.size()){ ll x = exp(1ll*cnt,1ll*(arr[i].f-cur)); ans = ans*x%MOD; cur = arr[i].f; ++i; --cnt; } return ans; }
Compilation message
# | 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 | 0 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 344 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 1 ms | 348 KB | Output is correct |
6 | Correct | 6 ms | 2396 KB | Output is correct |
7 | Correct | 16 ms | 4240 KB | Output is correct |
8 | Correct | 11 ms | 4444 KB | Output is correct |
9 | Correct | 4 ms | 1628 KB | Output is correct |
10 | Correct | 16 ms | 5104 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 344 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 | 440 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 6 ms | 2360 KB | Output is correct |
7 | Correct | 16 ms | 4320 KB | Output is correct |
8 | Correct | 13 ms | 4404 KB | Output is correct |
9 | Correct | 4 ms | 1848 KB | Output is correct |
10 | Correct | 15 ms | 5012 KB | Output is correct |
11 | Correct | 0 ms | 604 KB | Output is correct |
12 | Correct | 0 ms | 344 KB | Output is correct |
13 | Correct | 8 ms | 2396 KB | Output is correct |
14 | Correct | 0 ms | 348 KB | Output is correct |
15 | Correct | 22 ms | 5212 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 | 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 | 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 | 0 ms | 348 KB | Output is correct |
10 | 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 | 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 |
9 | Correct | 0 ms | 348 KB | Output is correct |
10 | Correct | 1 ms | 452 KB | Output is correct |
11 | Correct | 5 ms | 1116 KB | Output is correct |
12 | Correct | 6 ms | 1112 KB | Output is correct |
13 | Correct | 9 ms | 1748 KB | Output is correct |
14 | Correct | 4 ms | 1116 KB | Output is correct |
15 | Correct | 14 ms | 2348 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 |
# | 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 | 344 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Incorrect | 0 ms | 348 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 344 KB | Output is correct |
2 | Correct | 1 ms | 440 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Incorrect | 0 ms | 348 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |
# | 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 | Incorrect | 0 ms | 440 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |