답안 #128181

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
128181	2019-07-10T13:43:42 Z	dolphingarlic	곤돌라 (IOI14_gondola)	C++14	75 / 100	23 ms	2404 KB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
#pragma GCC Optimize("O3")
#define FOR(i, x, y) for (int i = x; i < y; i++)
#define MOD 1000000009
typedef long long ll;
using namespace std;

int valid(int n, int inputSeq[]) {
    bool in[250001];
    FOR(i, 0, n) {
        if (in[inputSeq[i]]) return 0;
        in[inputSeq[i]] = true;
    }

    FOR(i, 0, n) {
        if (inputSeq[i] <= n) {
            FOR(j, 1, n + 1) {
                int k = (i + j - inputSeq[i]) % n;
                while (k < 0) k += n;
                if (inputSeq[k] <= n && inputSeq[k] != j) return 0;
            }
            return 1;
        }
    }
    return 1;
}

//----------------------

int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
    vector<pair<int, int>> broken;
    int offset = 0;
    FOR(i, 0, n) {
        if (gondolaSeq[i] > n)
            broken.push_back({gondolaSeq[i], i + 1});
        else
            offset = i - gondolaSeq[i] + 1;
    }
    FOR(i, 0, broken.size()) {
        broken[i].second = (broken[i].second - offset - 1 + n) % n + 1;
    }

    int indx = 0, curr = n;
    sort(broken.begin(), broken.end());
    for (pair<int, int> i : broken) {
        replacementSeq[indx++] = i.second;
        curr++;
        FOR(j, curr, i.first)
        replacementSeq[indx++] = j;
        curr = i.first;
    }

    return indx;
}

//----------------------

ll expo(ll x, ll y) {
    ll res = 1;
    x = x % MOD;
    while (y > 0) {
        if (y & 1) res = (res * x) % MOD;
        y = y >> 1;
        x = (x * x) % MOD;
    }
    return res;
}

int countReplacement(int n, int inputSeq[]) {
    if (!valid(n, inputSeq)) return 0;
    // If there are k replaced cars {a, b}, {c, d}, ...
    // Then ans is k^(d - b) * (k - 1)^(f - d) + ...
    vector<ll> broken;
    broken.push_back(0);
    FOR(i, 0, n) {
        if (inputSeq[i] > n)
            broken.push_back(inputSeq[i] - n);
    }
    sort(broken.begin(), broken.end());
    ll ans = 1;
    FOR(i, 1, broken.size()) {
        ans = (ans * expo(broken.size() - i, broken[i] - broken[i - 1] - 1)) % MOD;
    }
    return ans;
}

Compilation message

gondola.cpp:3:0: warning: ignoring #pragma GCC Optimize [-Wunknown-pragmas]
 #pragma GCC Optimize("O3")
 
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:4:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, x, y) for (int i = x; i < y; i++)
gondola.cpp:40:9:
     FOR(i, 0, broken.size()) {
         ~~~~~~~~~~~~~~~~~~~             
gondola.cpp:40:5: note: in expansion of macro 'FOR'
     FOR(i, 0, broken.size()) {
     ^~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:4:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, x, y) for (int i = x; i < y; i++)
gondola.cpp:82:9:
     FOR(i, 1, broken.size()) {
         ~~~~~~~~~~~~~~~~~~~             
gondola.cpp:82:5: note: in expansion of macro 'FOR'
     FOR(i, 1, broken.size()) {
     ^~~
gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:12:27: warning: 'in[<unknown>]' may be used uninitialized in this function [-Wmaybe-uninitialized]
         if (in[inputSeq[i]]) return 0;
             ~~~~~~~~~~~~~~^

Subtask #1

5.0 / 5.0

#	결과	실행 시간	메모리	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	Correct	2 ms	376 KB	Output is correct

Subtask #2

5.0 / 5.0

#	결과	실행 시간	메모리	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	Correct	3 ms	376 KB	Output is correct
6	Correct	7 ms	760 KB	Output is correct
7	Correct	14 ms	1256 KB	Output is correct
8	Correct	12 ms	1144 KB	Output is correct
9	Correct	5 ms	632 KB	Output is correct
10	Correct	15 ms	1276 KB	Output is correct

Subtask #3

10.0 / 10.0

#	결과	실행 시간	메모리	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	Correct	2 ms	376 KB	Output is correct
6	Correct	7 ms	760 KB	Output is correct
7	Correct	14 ms	1272 KB	Output is correct
8	Correct	23 ms	1144 KB	Output is correct
9	Correct	6 ms	504 KB	Output is correct
10	Correct	14 ms	1272 KB	Output is correct
11	Correct	3 ms	376 KB	Output is correct
12	Correct	3 ms	376 KB	Output is correct
13	Correct	8 ms	888 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	15 ms	1304 KB	Output is correct

Subtask #4

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	0 ms	248 KB	Output is correct
4	Correct	2 ms	256 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct

Subtask #5

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	2 ms	380 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	3 ms	376 KB	Output is correct
7	Correct	3 ms	376 KB	Output is correct
8	Correct	3 ms	376 KB	Output is correct
9	Correct	3 ms	376 KB	Output is correct
10	Correct	3 ms	376 KB	Output is correct

Subtask #6

20.0 / 20.0

#	결과	실행 시간	메모리	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	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	3 ms	376 KB	Output is correct
9	Correct	3 ms	376 KB	Output is correct
10	Correct	3 ms	376 KB	Output is correct
11	Correct	12 ms	1144 KB	Output is correct
12	Correct	13 ms	1200 KB	Output is correct
13	Correct	18 ms	1548 KB	Output is correct
14	Correct	12 ms	1016 KB	Output is correct
15	Correct	23 ms	2404 KB	Output is correct

Subtask #7

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	300 KB	Output is correct

Subtask #8

15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	476 KB	Output is correct
2	Correct	2 ms	360 KB	Output is correct
3	Correct	3 ms	376 KB	Output is correct
4	Correct	2 ms	256 KB	Output is correct
5	Correct	2 ms	404 KB	Output is correct
6	Correct	2 ms	304 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct

Subtask #9

0 / 15.0

#	결과	실행 시간	메모리	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	3 ms	508 KB	Output is correct
7	Correct	5 ms	376 KB	Output is correct
8	Correct	2 ms	396 KB	Output is correct
9	Correct	21 ms	1780 KB	Output is correct
10	Correct	17 ms	1784 KB	Output is correct
11	Correct	8 ms	1204 KB	Output is correct
12	Correct	10 ms	1120 KB	Output is correct
13	Incorrect	4 ms	504 KB	Output isn't correct

Subtask #10

0 / 10.0

#	결과	실행 시간	메모리	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	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	21 ms	1880 KB	Output is correct
10	Correct	19 ms	1780 KB	Output is correct
11	Correct	8 ms	1144 KB	Output is correct
12	Correct	10 ms	1144 KB	Output is correct
13	Incorrect	4 ms	636 KB	Output isn't correct
14	Halted	0 ms	0 KB	-