# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
166618 |
2019-12-03T06:09:47 Z |
TAISA_ |
Gondola (IOI14_gondola) |
C++14 |
|
47 ms |
4600 KB |
#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using ll = long long;
int valid(int n, int inputSeq[]) {
int b = -1;
set<int> st;
for (int i = 0; i < n; i++) {
if (st.count(inputSeq[i])) {
return 0;
}
st.insert(inputSeq[i]);
if (inputSeq[i] <= n) {
if (b == -1) {
b = inputSeq[i];
} else {
if (b == n) {
if (inputSeq[i] != 1) {
return 0;
}
b = 1;
} else {
if (inputSeq[i] != b + 1) {
return 0;
}
b++;
}
}
} else {
if (b != -1) {
b++;
}
}
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
int ma = -1;
vector<int> co(250010), idx(n);
int id = 0;
int b = -1;
for (int i = 0; i < n; i++) {
if (gondolaSeq[i] <= n) {
if (b == -1) {
b = gondolaSeq[i];
for (int j = i; j < n; j++) {
idx[j] = b;
b++;
if (b == n + 1) {
b = 1;
}
}
for (int j = 0; j < i; j++) {
idx[j] = b;
b++;
if (b == n + 1) {
b = 1;
}
}
break;
}
}
}
if (b == -1) {
for (int i = 0; i < n; i++) {
idx[i] = i + 1;
}
}
vector<P> v;
for (int i = 0; i < n; i++) {
if (gondolaSeq[i] > n) {
ma = max(ma, gondolaSeq[i]);
v.push_back(P(gondolaSeq[i], i));
co[gondolaSeq[i]] = 1;
}
}
sort(v.begin(), v.end());
int t = n + 1;
for (int i = 0; i < v.size(); i++) {
replacementSeq[id] = idx[v[i].second];
id++;
for (int j = t; j < gondolaSeq[v[i].second]; j++) {
replacementSeq[id] = j;
id++;
}
t = gondolaSeq[v[i].second] + 1;
}
return id;
}
//----------------------
const ll MOD = 1000000009LL;
ll mpow(ll x, ll n) {
ll res = 1;
while (n > 0) {
if (n & 1) {
res *= x;
res %= MOD;
}
x *= x;
x %= MOD;
n >>= 1;
}
return res;
}
int countReplacement(int n, int inputSeq[]) {
if (!valid(n, inputSeq)) {
return 0;
}
int ma = -1;
vector<int> idx(n);
int id = 0;
int b = -1;
for (int i = 0; i < n; i++) {
if (inputSeq[i] <= n) {
if (b == -1) {
b = inputSeq[i];
for (int j = i; j < n; j++) {
idx[j] = b;
b++;
if (b == n + 1) {
b = 1;
}
}
for (int j = 0; j < i; j++) {
idx[j] = b;
b++;
if (b == n + 1) {
b = 1;
}
}
break;
}
}
}
ll res = 1;
if (b == -1) {
for (ll i = 1; i <= n; i++) {
res *= i;
res %= MOD;
}
for (int i = 0; i < n; i++) {
idx[i] = i + 1;
}
}
vector<P> v;
for (int i = 0; i < n; i++) {
if (inputSeq[i] > n) {
v.push_back(P(inputSeq[i], i));
}
}
sort(v.begin(), v.end());
ll co = v.size();
b = n + 1;
for (int i = 0; i < v.size(); i++) {
res *= mpow(co, v[i].first - b);
res %= MOD;
--co;
b = v[i].first + 1;
}
return res;
}
Compilation message
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:83:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < v.size(); i++) {
~~^~~~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:159:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < v.size(); i++) {
~~^~~~~~~~~~
gondola.cpp:114:9: warning: unused variable 'ma' [-Wunused-variable]
int ma = -1;
^~
gondola.cpp:116:9: warning: unused variable 'id' [-Wunused-variable]
int id = 0;
^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
2 ms |
380 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
252 KB |
Output is correct |
2 |
Correct |
2 ms |
252 KB |
Output is correct |
3 |
Correct |
2 ms |
256 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
20 ms |
2240 KB |
Output is correct |
7 |
Correct |
13 ms |
632 KB |
Output is correct |
8 |
Correct |
35 ms |
4088 KB |
Output is correct |
9 |
Correct |
12 ms |
1528 KB |
Output is correct |
10 |
Correct |
47 ms |
4600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
19 ms |
2296 KB |
Output is correct |
7 |
Correct |
13 ms |
632 KB |
Output is correct |
8 |
Correct |
34 ms |
3960 KB |
Output is correct |
9 |
Correct |
13 ms |
1528 KB |
Output is correct |
10 |
Correct |
46 ms |
4472 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
7 ms |
504 KB |
Output is correct |
14 |
Correct |
2 ms |
380 KB |
Output is correct |
15 |
Correct |
14 ms |
636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1272 KB |
Output is correct |
2 |
Correct |
3 ms |
1272 KB |
Output is correct |
3 |
Correct |
3 ms |
1272 KB |
Output is correct |
4 |
Correct |
3 ms |
1272 KB |
Output is correct |
5 |
Correct |
3 ms |
1400 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1272 KB |
Output is correct |
2 |
Correct |
3 ms |
1276 KB |
Output is correct |
3 |
Correct |
3 ms |
1272 KB |
Output is correct |
4 |
Correct |
5 ms |
1400 KB |
Output is correct |
5 |
Correct |
3 ms |
1276 KB |
Output is correct |
6 |
Correct |
3 ms |
1272 KB |
Output is correct |
7 |
Correct |
3 ms |
1272 KB |
Output is correct |
8 |
Correct |
3 ms |
1400 KB |
Output is correct |
9 |
Correct |
3 ms |
1400 KB |
Output is correct |
10 |
Correct |
3 ms |
1272 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1272 KB |
Output is correct |
2 |
Correct |
3 ms |
1272 KB |
Output is correct |
3 |
Correct |
3 ms |
1272 KB |
Output is correct |
4 |
Correct |
3 ms |
1272 KB |
Output is correct |
5 |
Correct |
3 ms |
1272 KB |
Output is correct |
6 |
Correct |
3 ms |
1272 KB |
Output is correct |
7 |
Correct |
3 ms |
1400 KB |
Output is correct |
8 |
Correct |
3 ms |
1400 KB |
Output is correct |
9 |
Correct |
3 ms |
1400 KB |
Output is correct |
10 |
Correct |
3 ms |
1400 KB |
Output is correct |
11 |
Correct |
13 ms |
1912 KB |
Output is correct |
12 |
Correct |
14 ms |
2040 KB |
Output is correct |
13 |
Correct |
19 ms |
2292 KB |
Output is correct |
14 |
Correct |
13 ms |
1912 KB |
Output is correct |
15 |
Correct |
25 ms |
2420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
252 KB |
Output is correct |
3 |
Correct |
2 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |