Submission #107958

#	Time	Username	Problem	Language	Result	Execution time	Memory
107958		PeppaPig	Gondola (IOI14_gondola)	C++14	70 / 100	104 ms	6136 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>

#define long long long
#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 1e5+5;
const int M = 1e9+9;

int valid(int n, int A[]) {
    set<int> S(A, A + n);
    if((int)S.size() != n) return 0;
    for(int i = 0, k = -M; i < n; i++) if(A[i] <= n) {
        if(k == -M) k = (A[i] - i - 1 + n) % n;
        else if(k != (A[i] - i - 1 + n) % n) return 0;
    }
    return 1;
}

int replacement(int n, int A[], int ret[]) {
    int k = -M, ptr = 0, B[N];
    for(int i = 0; i < n; i++) if(A[i] <= n) k = (A[i] - i - 1 + n) % n;

    vector<pii> v;
    if(k == -M) iota(B, B+n, 1);
    else for(int i = 0; i < n; i++) {
        B[i] = A[(i - k + n) % n];
        if(B[i] > n) v.emplace_back(B[i], i+1);
    }
    sort(v.begin(), v.end());
    for(int i = 0; i < (int)v.size(); i++) while(ptr + n < v[i].x) {
        ret[ptr++] = v[i].y;
        v[i].y = ptr + n;
    }
    return ptr;
}

long modpow(long a, long b) {
    long ret = 1;
    for( ; b; b >>= 1) {
        if(b & 1) ret = (ret * a) % M;
        a = (a * a) % M;
    }
    return ret;
}

int countReplacement(int n, int A[]) {
    if(!valid(n, A)) return 0;

    vector<int> v;
    for(int i = 0; i < n; i++) if(A[i] > n) v.emplace_back(A[i]);
    sort(v.begin(), v.end());

    long ans = 1;
    for(int i = 0; i < (int)v.size(); i++) {
        int b = v.size() - i;
        int p = v[i] - (i ? v[i-1] + 1 : n + 1);
        ans = (ans * modpow(b, p)) % M;
    }
    if((int)v.size() == n) ans = (ans * n) % M;

    return ans;
}

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