oj.uz

Submission #936341

# Submission time Handle Problem Language Result Execution time Memory
936341 2024-03-01T16:25:54 Z peterandvoi Gondola (IOI14_gondola) C++17
75 / 100
 24 ms 7668 KB 
#include <bits/stdc++.h>
 
#include "gondola.h"
 
using namespace std;
 
#ifdef ngu
#include "debug.h"
#else
#define debug(...) 42
#endif
 
const int N = 250005;
 
int cnt[N];
 
int shift(int i, int j, int n) {
    i += j;
    if (i < 1) {
        i += n;
    }
    if (i > n) {
        i -= n;
    }
    return i;
}
 
int valid(int n, int inputSeq[]) {
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < n; ++i) {
        assert(inputSeq[i] < N);
        if (cnt[inputSeq[i]]) {
            return 0;
        }
        cnt[inputSeq[i]]++;
    }
    int delta = 0;
    for (int i = 0; i < n; ++i) {
        if (inputSeq[i] <= n) {
            int j = inputSeq[i];
            delta = j - i - 1;
            break;
        }
    }
    for (int i = 0; i < n; ++i) {
        if (inputSeq[i] <= n) {
            int j = shift(i + 1, delta, n);
            if (j != inputSeq[i]) {
                return 0;
            }
        }
    }
    return 1;
}
 
int pos[N];
 
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
    memset(pos, -1, sizeof(pos));
    for (int i = 0; i < n; ++i) {
        pos[gondolaSeq[i]] = i;
    }
    set<int> cur;
    for (int i = 0; i < n; ++i) {
        cur.insert(i);
    }
    for (int i = 0; i < n; ++i) {
        if (gondolaSeq[i] <= n) {
            cur.erase(i);
        }
    }
    int delta = 0;
    for (int i = 0; i < n; ++i) {
        if (gondolaSeq[i] <= n) {
            int j = gondolaSeq[i];
            delta = j - i - 1;
            break;
        }
    }
    for (int i = 0; i < n; ++i) {
        gondolaSeq[i] = shift(i + 1, delta, n);
    }
    int m = -1;
    for (int i = n + 1; i < N; ++i) {
        if (!cur.size()) {
            break;
        }
        int j = *cur.begin();
        if (pos[i] != -1) {
            j = pos[i];
            cur.erase(j);
        }
        replacementSeq[++m] = gondolaSeq[j];
        gondolaSeq[j] = i;
    }
    return m + 1;
}
 
const int MOD = (int) 1e9 + 9;
 
int countReplacement(int n, int inputSeq[]) {
    if (valid(n, inputSeq) == 0) {
        return 0;
    }
    memset(pos, -1, sizeof(pos));
    for (int i = 0; i < n; ++i) {
        pos[inputSeq[i]] = i;
    }
    int cnt = n;
    for (int i = 0; i < n; ++i) {
        if (inputSeq[i] <= n) {
            cnt--;
        }
    }
    int res = 1;
    int delta = 0;
    for (int i = 0; i < n; ++i) {
        if (inputSeq[i] <= n) {
            int j = inputSeq[i];
            delta = j - i - 1;
            break;
        }
    }
    for (int i = 0; i < n; ++i) {
        inputSeq[i] = shift(i + 1, delta, n);
    }
    for (int i = n + 1; i < N; ++i) {
        if (!cnt) {
            break;
        }
        if (pos[i] != -1) {
            cnt--;
        } else {
            res = 1LL * res * cnt % MOD;
        }
    }
    if (cnt == n) {
        res = 1LL * res * n % MOD;
    }
    return res;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 4 ms 2652 KB Output is correct
7 Correct 10 ms 3164 KB Output is correct
8 Correct 6 ms 3164 KB Output is correct
9 Correct 2 ms 2652 KB Output is correct
10 Correct 8 ms 3164 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2440 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 4 ms 2652 KB Output is correct
7 Correct 8 ms 3164 KB Output is correct
8 Correct 8 ms 3164 KB Output is correct
9 Correct 2 ms 2652 KB Output is correct
10 Correct 7 ms 3164 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 4 ms 2652 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 10 ms 3160 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2648 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2848 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2648 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2648 KB Output is correct
11 Correct 21 ms 7004 KB Output is correct
12 Correct 24 ms 7668 KB Output is correct
13 Correct 22 ms 4828 KB Output is correct
14 Correct 23 ms 6952 KB Output is correct
15 Correct 20 ms 5060 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2492 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2476 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2648 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2648 KB Output is correct
9 Correct 8 ms 3416 KB Output is correct
10 Correct 7 ms 3160 KB Output is correct
11 Correct 3 ms 2908 KB Output is correct
12 Correct 4 ms 2952 KB Output is correct
13 Incorrect 2 ms 2652 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2848 KB Output is correct
3 Correct 1 ms 2904 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 9 ms 3420 KB Output is correct
10 Correct 6 ms 3160 KB Output is correct
11 Correct 4 ms 2908 KB Output is correct
12 Correct 4 ms 2904 KB Output is correct
13 Incorrect 2 ms 2504 KB Output isn't correct
14 Halted 0 ms 0 KB -