#include "gondola.h"
#include <bits/stdc++.h>
#ifdef local
#define debug(...) qqbx(#__VA_ARGS__, __VA_ARGS__)
void qqbx(const char *s) {}
template <typename H, typename ...T> void qqbx(const char *s, const H& h, T&& ...args) {
for(; *s && *s != ','; ++s) if(*s != ' ') std::cerr << *s;
std::cerr << " = " << h << (sizeof...(T) ? ", " : "\n");
if(sizeof...(T)) qqbx(++s, args...);
}
#define safe std::cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#else
#define debug(...) ((void)0)
#define safe ((void)0)
#endif // local
#define pb emplace_back
#define all(v) begin(v),end(v)
using namespace std;
int valid(int n, int inputSeq[]) {
vector<int> v(inputSeq, inputSeq+n), u = v;
sort(u.begin(), u.end());
for(int i = 1; i < n; i++) if(u[i] == u[i-1]) return false;
for(int &x: v) --x;
queue<int> q;
for(int i = 0; i < n; i++) if(v[i] < n) q.push(i);
while(!q.empty()) {
int i = q.front(); q.pop();
int j = (i+1)%n;
if(v[j] >= n) {
v[j] = (v[i]+1)%n;
q.push(j);
} else if(v[j] != (v[i]+1)%n) {
return false;
}
}
return true;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
int L = 0;
int tot = n;
vector<int> v(gondolaSeq, gondolaSeq+n), org = v;
{
for(int &x: org) --x;
queue<int> q;
for(int i = 0; i < n; i++) if(org[i] < n) q.push(i);
if(q.empty()) {
for(int i = 0; i < n; i++) org[i] = i+1;
} else {
while(!q.empty()) {
int i = q.front(); q.pop();
int j = (i+1)%n;
if(org[j] >= n) {
org[j] = (org[i]+1)%n;
q.push(j);
} else {
assert(org[j] == (org[i]+1)%n);
}
}
for(int &x: org) ++x;
}
}
vector<pair<int,int>> evt;
for(int i = 0; i < n; i++) if(v[i] > n) evt.pb(v[i], i);
sort(evt.begin(), evt.end());
for(int i = 0; i < int(evt.size()); i++)
while(tot < evt[i].first) replacementSeq[L++] = org[evt[i].second], org[evt[i].second] = ++tot;
return L;
}
//----------------------
const int MOD = 1000000009;
int modpow(long long e, int p) {
long long r = 1;
for(; p; p>>=1, e=e*e%MOD) if(p&1) r = r*e%MOD;
return r;
}
int countReplacement(int n, int inputSeq[]) {
if(!valid(n, inputSeq)) return 0;
vector<int> v(inputSeq, inputSeq+n);
vector<pair<int,int>> evt;
for(int i = 0; i < n; i++) if(v[i] > n) evt.pb(v[i], i);
sort(evt.begin(), evt.end());
int tot = n;
long long ans = 1;
for(int i = 0; i < int(evt.size()); i++) {
// tot+1, tot+2, ... evt[i].first-1 can be arbitary placed on evt.size()-i positions
debug(evt.size()-i, evt[i].first - tot);
ans = ans * modpow(int(evt.size()) - i, evt[i].first - tot - 1) % MOD;
tot = evt[i].first;
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
288 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
0 ms |
256 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
0 ms |
256 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
9 ms |
1024 KB |
Output is correct |
7 |
Correct |
20 ms |
1408 KB |
Output is correct |
8 |
Correct |
15 ms |
1408 KB |
Output is correct |
9 |
Correct |
6 ms |
640 KB |
Output is correct |
10 |
Correct |
20 ms |
1664 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
256 KB |
Output is correct |
6 |
Correct |
9 ms |
896 KB |
Output is correct |
7 |
Correct |
20 ms |
1408 KB |
Output is correct |
8 |
Correct |
15 ms |
1408 KB |
Output is correct |
9 |
Correct |
6 ms |
640 KB |
Output is correct |
10 |
Correct |
26 ms |
1656 KB |
Output is correct |
11 |
Correct |
1 ms |
256 KB |
Output is correct |
12 |
Correct |
0 ms |
256 KB |
Output is correct |
13 |
Correct |
9 ms |
768 KB |
Output is correct |
14 |
Correct |
1 ms |
256 KB |
Output is correct |
15 |
Correct |
22 ms |
1664 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
256 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
0 ms |
256 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
256 KB |
Output is correct |
6 |
Correct |
0 ms |
256 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
15 ms |
1536 KB |
Output is correct |
12 |
Correct |
17 ms |
1792 KB |
Output is correct |
13 |
Correct |
21 ms |
1404 KB |
Output is correct |
14 |
Correct |
14 ms |
1536 KB |
Output is correct |
15 |
Correct |
28 ms |
2416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
372 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Correct |
1 ms |
360 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
26 ms |
1984 KB |
Output is correct |
10 |
Correct |
22 ms |
1952 KB |
Output is correct |
11 |
Correct |
9 ms |
1104 KB |
Output is correct |
12 |
Correct |
11 ms |
1164 KB |
Output is correct |
13 |
Incorrect |
3 ms |
512 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
26 ms |
1984 KB |
Output is correct |
10 |
Correct |
25 ms |
1952 KB |
Output is correct |
11 |
Correct |
9 ms |
1104 KB |
Output is correct |
12 |
Correct |
13 ms |
1064 KB |
Output is correct |
13 |
Incorrect |
3 ms |
512 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |