# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
257426 |
2020-08-04T09:08:20 Z |
Berted |
Gondola (IOI14_gondola) |
C++14 |
|
41 ms |
5384 KB |
#include "gondola.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <unordered_map>
#define pii pair<int, int>
#define fst first
#define snd second
#define ll long long
const int MD = 1e9 + 9;
using namespace std;
inline ll pw(ll b, ll e)
{
ll t = 1;
while (e)
{
if (e & 1) {t = (t * b) % MD;}
b = (b * b) % MD; e >>= 1;
}
return t;
}
int valid(int n, int inputSeq[])
{
unordered_map<int, int> cnt; int sp = -1;
for (int i = 0; i < n; i++)
{
if (inputSeq[i] <= n)
{
if (sp == -1) sp = (i + (n + 1 - inputSeq[i])) % n;
else if (sp != (i + (n + 1 - inputSeq[i])) % n) {return 0;}
}
cnt[inputSeq[i]]++;
if (cnt[inputSeq[i]] > 1) {return 0;}
}
return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int sp = -1, lg = 0;
vector<pii> v;
for (int i = 0; i < n; i++)
{
if (gondolaSeq[i] <= n) {sp = (i + (n + 1 - gondolaSeq[i])) % n;}
else {v.push_back({gondolaSeq[i], i});}
}
if (sp == -1) {sp = 0;}
sort(v.begin(), v.end());
for (auto &x : v)
{
replacementSeq[lg++] = (x.snd + n - sp) % n + 1;
while (lg + n < x.fst) {replacementSeq[lg] = n + lg; lg++;}
}
return lg;
}
int countReplacement(int n, int inputSeq[])
{
if (!valid(n, inputSeq)) {return 0;}
vector<int> v; int sp = -1;
for (int i = 0; i < n; i++)
{
if (inputSeq[i] > n) {v.push_back(inputSeq[i]);}
else {sp = 0;}
}
sort(v.begin(), v.end());
int pv = n; long long res = 1;
for (int i = 0; i < v.size(); i++)
{
res = (res * pw(v.size() - i, v[i] - pv - 1)) % MD;
pv = v[i];
}
if (sp == -1) {res = (res * n) % MD;}
return res;
}
Compilation message
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:72:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < v.size(); i++)
~~^~~~~~~~~~
# |
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 |
256 KB |
Output is correct |
4 |
Correct |
1 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 |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 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 |
9 ms |
2224 KB |
Output is correct |
7 |
Correct |
14 ms |
1152 KB |
Output is correct |
8 |
Correct |
17 ms |
4112 KB |
Output is correct |
9 |
Correct |
6 ms |
1408 KB |
Output is correct |
10 |
Correct |
20 ms |
4608 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 |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
9 ms |
2224 KB |
Output is correct |
7 |
Correct |
14 ms |
1152 KB |
Output is correct |
8 |
Correct |
17 ms |
4112 KB |
Output is correct |
9 |
Correct |
6 ms |
1408 KB |
Output is correct |
10 |
Correct |
20 ms |
4624 KB |
Output is correct |
11 |
Correct |
0 ms |
384 KB |
Output is correct |
12 |
Correct |
0 ms |
256 KB |
Output is correct |
13 |
Correct |
6 ms |
640 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
14 ms |
1152 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 |
1 ms |
384 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 |
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 |
0 ms |
256 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
0 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 |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 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 |
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 |
0 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 |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
11 ms |
1024 KB |
Output is correct |
12 |
Correct |
13 ms |
1152 KB |
Output is correct |
13 |
Correct |
15 ms |
1544 KB |
Output is correct |
14 |
Correct |
12 ms |
1024 KB |
Output is correct |
15 |
Correct |
21 ms |
2424 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 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 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 |
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 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
0 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 |
0 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
256 KB |
Output is correct |
9 |
Correct |
41 ms |
4232 KB |
Output is correct |
10 |
Correct |
24 ms |
3888 KB |
Output is correct |
11 |
Correct |
9 ms |
1536 KB |
Output is correct |
12 |
Correct |
11 ms |
2048 KB |
Output is correct |
13 |
Correct |
3 ms |
768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 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 |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
0 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
384 KB |
Output is correct |
8 |
Correct |
0 ms |
256 KB |
Output is correct |
9 |
Correct |
31 ms |
4360 KB |
Output is correct |
10 |
Correct |
24 ms |
3888 KB |
Output is correct |
11 |
Correct |
13 ms |
1408 KB |
Output is correct |
12 |
Correct |
11 ms |
2048 KB |
Output is correct |
13 |
Correct |
3 ms |
768 KB |
Output is correct |
14 |
Correct |
37 ms |
4880 KB |
Output is correct |
15 |
Correct |
41 ms |
5384 KB |
Output is correct |
16 |
Correct |
8 ms |
1280 KB |
Output is correct |
17 |
Correct |
28 ms |
4136 KB |
Output is correct |
18 |
Correct |
17 ms |
2352 KB |
Output is correct |