oj.uz

Submission #637307

# Submission time Handle Problem Language Result Execution time Memory
637307 2022-09-01T10:09:18 Z ghostwriter Gondola (IOI14_gondola) C++14
100 / 100
 58 ms 5964 KB 
#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <debug.h>
#include "grader.cpp"
#endif
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
typedef long long ll; typedef unsigned long long ull;
typedef double db; typedef long double ldb;
typedef pair<int, int> pi; typedef pair<ll, ll> pll;
typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll;
typedef string str;
template<typename T> T gcd(T a, T b) { return (b == 0? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
#define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
#define EACH(i, x) for (auto &(i) : (x))
#define WHILE while
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
/*
    Tran The Bao
    CTL - Da Lat
    Cay ngay cay dem nhung deo duoc cong nhan
*/
bool checkdistinct(int n, int inputSeq[]) {
    map<int, int> c;  
    FOR(i, 0, n - 1) {
        ++c[inputSeq[i]];
        if (c[inputSeq[i]] > 1) return 0;
    }
    return 1;
}
int getoriginalpos(int n, int inputSeq[]) {
    FOR(i, 0, n - 1)
        if (inputSeq[i] <= n)
            return i;
    return -1;
}
int valid(int n, int inputSeq[]) {
    if (!checkdistinct(n, inputSeq)) return 0;
    int pos = getoriginalpos(n, inputSeq);
    if (pos == -1) return 1;
    FOR(i, 0, n - 1) {
        if (inputSeq[i] > n || i == pos) continue;
        int val = (i - pos + inputSeq[pos] - 1 + n) % n + 1;
        if (inputSeq[i] != val) return 0;
    }
    return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
    vpi a;
    int pos = getoriginalpos(n, gondolaSeq);
    if (pos == -1) pos = 0;
    FOR(i, 0, n - 1) {
        if (gondolaSeq[i] <= n) continue;
        int val = (i - pos + gondolaSeq[pos] - 1 + n) % n + 1;
        a.pb({gondolaSeq[i], val});
    }
    sort(all(a));
    int cur = n, l = 0;
    EACH(i, a) {
        replacementSeq[l++] = i.nd;
        ++cur;
        WHILE(cur < i.st) replacementSeq[l++] = cur++;
    }
    return l;
}

//----------------------
const int M = 1e9 + 9;
int fpow(int a, int b, int M) {
    if (b == 0) return 1;
    int tmp = fpow(a, b >> 1, M);
    if (b & 1) return 1LL * tmp * tmp % M * a % M;
    return 1LL * tmp * tmp % M;
}
int countReplacement(int n, int inputSeq[]) {
    if (!valid(n, inputSeq)) return 0;
    vi a;
    FOR(i, 0, n - 1) {
        if (inputSeq[i] <= n) continue;
        a.pb(inputSeq[i]);
    }
    if (a.empty()) return 1;
    sort(all(a));
    int pre = n, total = sz(a), rs = 1;
    EACH(i, a) {
        int cnt = i - pre - 1;
        rs = 1LL * rs * fpow(total, cnt, M) % M;
        pre = i;
        --total;
    }
    int pos = getoriginalpos(n, inputSeq);
    if (pos == -1) rs = 1LL * rs * n % M;
    return rs;
}
/*
10
4
4 7 4 7
*/

Compilation message

gondola.cpp: In function 'bool checkdistinct(int, int*)':
gondola.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
gondola.cpp:40:5: note: in expansion of macro 'FOR'
   40 |     FOR(i, 0, n - 1) {
      |     ^~~
gondola.cpp: In function 'int getoriginalpos(int, int*)':
gondola.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
gondola.cpp:47:5: note: in expansion of macro 'FOR'
   47 |     FOR(i, 0, n - 1)
      |     ^~~
gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
gondola.cpp:56:5: note: in expansion of macro 'FOR'
   56 |     FOR(i, 0, n - 1) {
      |     ^~~
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
gondola.cpp:70:5: note: in expansion of macro 'FOR'
   70 |     FOR(i, 0, n - 1) {
      |     ^~~
gondola.cpp:28:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   28 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
gondola.cpp:77:5: note: in expansion of macro 'EACH'
   77 |     EACH(i, a) {
      |     ^~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
gondola.cpp:96:5: note: in expansion of macro 'FOR'
   96 |     FOR(i, 0, n - 1) {
      |     ^~~
gondola.cpp:28:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   28 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
gondola.cpp:103:5: note: in expansion of macro 'EACH'
  103 |     EACH(i, a) {
      |     ^~~~

Subtask #1
5.0 / 5.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 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #2
5.0 / 5.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
6 Correct 13 ms 2204 KB Output is correct
7 Correct 8 ms 576 KB Output is correct
8 Correct 27 ms 3912 KB Output is correct
9 Correct 7 ms 1364 KB Output is correct
10 Correct 28 ms 4416 KB Output is correct

Subtask #3
10.0 / 10.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 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 12 ms 2100 KB Output is correct
7 Correct 8 ms 596 KB Output is correct
8 Correct 23 ms 3840 KB Output is correct
9 Correct 8 ms 1364 KB Output is correct
10 Correct 29 ms 4436 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 2056 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 40 ms 4684 KB Output is correct

Subtask #4
5.0 / 5.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 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #5
10.0 / 10.0

# 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 1 ms 232 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 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

Subtask #6
20.0 / 20.0

# 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 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 256 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 2 ms 304 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 6 ms 596 KB Output is correct
12 Correct 8 ms 596 KB Output is correct
13 Correct 13 ms 1280 KB Output is correct
14 Correct 6 ms 596 KB Output is correct
15 Correct 20 ms 2252 KB Output is correct

Subtask #7
5.0 / 5.0

# 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

Subtask #8
15.0 / 15.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 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

Subtask #9
15.0 / 15.0

# 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 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 36 ms 3924 KB Output is correct
10 Correct 29 ms 3284 KB Output is correct
11 Correct 10 ms 1364 KB Output is correct
12 Correct 14 ms 1704 KB Output is correct
13 Correct 3 ms 596 KB Output is correct

Subtask #10
10.0 / 10.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 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 37 ms 3992 KB Output is correct
10 Correct 30 ms 3412 KB Output is correct
11 Correct 11 ms 1444 KB Output is correct
12 Correct 15 ms 1700 KB Output is correct
13 Correct 3 ms 596 KB Output is correct
14 Correct 48 ms 4464 KB Output is correct
15 Correct 58 ms 5964 KB Output is correct
16 Correct 9 ms 1296 KB Output is correct
17 Correct 35 ms 4076 KB Output is correct
18 Correct 21 ms 2388 KB Output is correct