Submission #637305

#	Time	Username	Problem	Language	Result	Execution time	Memory
637305		ghostwriter	Gondola (IOI14_gondola)	C++14	90 / 100	19 ms	3028 KiB

gondola

#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
*/
const int MAXA = 25e4 + 1;
bool checkdistinct(int n, int inputSeq[]) {
    vi c(MAXA, 0);
    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;
    bool ok = 0;
    FOR(i, 0, n - 1) {
        if (inputSeq[i] <= n) continue;
        if (inputSeq[i] >= MAXA) ok = 1;
        a.pb(inputSeq[i]);
    }
    if (ok) assert(0 > 1);
    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 (stderr)

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:41:5: note: in expansion of macro 'FOR'
   41 |     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:48:5: note: in expansion of macro 'FOR'
   48 |     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:57:5: note: in expansion of macro 'FOR'
   57 |     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:71:5: note: in expansion of macro 'FOR'
   71 |     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:78:5: note: in expansion of macro 'EACH'
   78 |     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:98:5: note: in expansion of macro 'FOR'
   98 |     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:107:5: note: in expansion of macro 'EACH'
  107 |     EACH(i, a) {
      |     ^~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 20 / 20
• Subtask 7: 5 / 5
• Subtask 8: 15 / 15
• Subtask 9: 15 / 15
• Subtask 10: 0 / 10