# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
587077 |
2022-07-01T09:39:27 Z |
hibiki |
Gondola (IOI14_gondola) |
C++11 |
|
54 ms |
5876 KB |
#include "gondola.h"
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000009
#define pb push_back
#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
int valid(int n, int a[])
{
map<int,bool> use;
pair<int,int> mn = {1e9, 1e9};
for(int i = 0; i < n; i++)
{
mn = min(mn, {a[i], i});
if(use.count(a[i])) return 0;
use[a[i]] = true;
}
if(mn.f > n) return 1;
if(mn.f < 1) return 0;
for(int i = 0; i < n; i++)
{
if(a[(mn.s + i) % n] <= n && a[(mn.s + i) % n] != (mn.f + i + n - 1) % n + 1)
return 0;
}
return 1;
}
//----------------------
int to[250005], use[250005];
int replacement(int n, int a[], int ans[])
{
int mx = 0;
int cur = -1, idx = 0;
pair<int,int> mn = {1e9, 1e9};
for(int i = 0; i < n; i++)
mn = min(mn, {a[i], i}), mx = max(mx, a[i]);
for(int i = 0; i < n; i++)
if(a[(mn.s + i) % n] != (mn.f + i + n - 1) % n + 1)
{
to[(mn.f + i + n - 1) % n + 1] = a[(mn.s + i) % n];
if(a[(mn.s + i) % n] == mx)
cur = (mn.f + i + n - 1) % n + 1;
else
use[a[(mn.s + i) % n]] = (mn.f + i + n - 1) % n + 1;
}
for(int i = n + 1; i <= mx; i++)
{
if(use[i])
ans[idx++] = use[i];
else
ans[idx++] = cur, cur = i;
}
return idx;
}
//----------------------
int fast_pow(long long base, long long pw)
{
if(pw == 0) return 1;
long long ret = 1ll;
long long mul = base;
while(pw > 0)
{
if(pw & 1)
ret = (ret * mul) % mod;
mul = (mul * mul) % mod;
pw >>= 1;
}
return ret;
}
int countReplacement(int n, int a[])
{
if(!valid(n, a)) return 0;
int mx = 0;
vector<int> v;
long long cal = 1ll;
pair<int,int> mn = {1e9, 1e9};
for(int i = 0; i < n; i++)
{
mn = min(mn, {a[i], i});
if(a[i] > n) v.pb(a[i]);
}
if(mn.f > n)
cal *= n;
v.pb(n);
sort(all(v));
for(int i = 1; i < sz(v); i++)
{
if(v[i] - v[i - 1] - 1 == 0) continue;
cal *= fast_pow((sz(v) - i), (v[i] - v[i - 1] - 1));
cal %= mod;
}
return cal;
}
Compilation message
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:81:9: warning: unused variable 'mx' [-Wunused-variable]
81 | int mx = 0;
| ^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
16 ms |
2116 KB |
Output is correct |
7 |
Correct |
9 ms |
596 KB |
Output is correct |
8 |
Correct |
21 ms |
3924 KB |
Output is correct |
9 |
Correct |
7 ms |
1364 KB |
Output is correct |
10 |
Correct |
28 ms |
4516 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
12 ms |
2116 KB |
Output is correct |
7 |
Correct |
8 ms |
596 KB |
Output is correct |
8 |
Correct |
23 ms |
3912 KB |
Output is correct |
9 |
Correct |
7 ms |
1364 KB |
Output is correct |
10 |
Correct |
31 ms |
4572 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
15 ms |
2040 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
37 ms |
4596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
7 ms |
552 KB |
Output is correct |
12 |
Correct |
8 ms |
596 KB |
Output is correct |
13 |
Correct |
10 ms |
1492 KB |
Output is correct |
14 |
Correct |
7 ms |
616 KB |
Output is correct |
15 |
Correct |
17 ms |
2672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
39 ms |
4032 KB |
Output is correct |
10 |
Correct |
32 ms |
3340 KB |
Output is correct |
11 |
Correct |
12 ms |
1364 KB |
Output is correct |
12 |
Correct |
17 ms |
1620 KB |
Output is correct |
13 |
Correct |
3 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
47 ms |
3964 KB |
Output is correct |
10 |
Correct |
32 ms |
3284 KB |
Output is correct |
11 |
Correct |
14 ms |
1368 KB |
Output is correct |
12 |
Correct |
14 ms |
1700 KB |
Output is correct |
13 |
Correct |
4 ms |
596 KB |
Output is correct |
14 |
Correct |
47 ms |
4460 KB |
Output is correct |
15 |
Correct |
54 ms |
5876 KB |
Output is correct |
16 |
Correct |
9 ms |
1364 KB |
Output is correct |
17 |
Correct |
35 ms |
4032 KB |
Output is correct |
18 |
Correct |
19 ms |
2388 KB |
Output is correct |