Submission #54512

#	Time	Username	Problem	Language	Result	Execution time	Memory
54512		updown1	Gondola (IOI14_gondola)	C++17	100 / 100	217 ms	16364 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, n)
#define ffj For(j, 0, n)
#define ffa ffi ffj
#define s <<" "<<
#define w cout
#define e "\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
//#define int ll
const int MAXN=100000, MOD=1000000009;
 
int valid(int n, int inputSeq[]) {
    set<int> have;
    ffi have.insert(inputSeq[i]);
    if (have.size() != n) return 0;
    int correct[MAXN];
    ffi if (inputSeq[i] <= n) {
        correct[i] = inputSeq[i];
        For (j, i+1, n) {
            correct[j] = 1+correct[j-1];
            if (correct[j] == n+1) correct[j] = 1;
        }
        correct[0] = 1+correct[n-1];
        if (correct[0] == n+1) correct[0] = 1;
        For (j, 1, i) {
            correct[j] = 1+correct[j-1];
            if (correct[j] == n+1) correct[j] = 1;
        }
        break;
    }
    ffi if (inputSeq[i] != correct[i] && inputSeq[i] <= n) return 0;
    return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
    int correct[MAXN];
    ffi correct[i] = i+1;
    ffi if (gondolaSeq[i] <= n) {
        correct[i] = gondolaSeq[i];
        For (j, i+1, n) {
            correct[j] = 1+correct[j-1];
            if (correct[j] == n+1) correct[j] = 1;
        }
        correct[0] = 1+correct[n-1];
        if (correct[0] == n+1) correct[0] = 1;
        For (j, 1, i) {
            correct[j] = 1+correct[j-1];
            if (correct[j] == n+1) correct[j] = 1;
        }
        break;
    }
    int at = 0;
    int val = 0, save;
    ffi if (gondolaSeq[i] > val) val = gondolaSeq[i], save = i;
    int loc[250001];
    For (i, 0, 250001) loc[i] = -1;
    ffi loc[gondolaSeq[i]] = i;
    For (i, n+1, val+1) {
        if (loc[i] == -1) {
            replacementSeq[at] = correct[save];
            correct[save] = i;
            at++;
        }
        else {
            replacementSeq[at] = correct[loc[i]];
            correct[loc[i]] = i;
            at++;
        }
    }
    return at;
}
int countReplacement(int n, int inputSeq[]) {
    if (valid(n, inputSeq) == 0) return 0;
    ll ret = 1;
    set<int> have;
    int big = 0;
    ffi if (inputSeq[i] > n) have.insert(inputSeq[i]), big = max(big, inputSeq[i]);
    int at = n+1;
    ll base = have.size();
    ll pb[31];
    for (int i: have) {
        int p = i-at;
        pb[0] = base;
        //w<< base s p <<e;
        For (i, 1, 31) pb[i] = pb[i-1]*pb[i-1], pb[i] %= MOD;
        For (i, 0, 31) if (p & (1<<i)) {
            //w<<i s (1<<i) s pb[i]<<e;
            ret *= pb[i];
            ret %= MOD;
        }
        //w<< ret<<e;
        base--;
        at = i+1;
    }
    bool small = false;
    ffi if (inputSeq[i] <= n) small = true;
    if (!small) ret *= n, ret %= MOD;
    return ret;
}

Compilation message (stderr)

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:22:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (have.size() != n) return 0;
         ~~~~~~~~~~~~^~~~
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:66:46: warning: 'save' may be used uninitialized in this function [-Wmaybe-uninitialized]
             replacementSeq[at] = correct[save];
                                  ~~~~~~~~~~~~^

• 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: 10 / 10