Submission #1218250

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218250		Hamed_Ghaffari	Gondola (IOI14_gondola)	C++20	100 / 100	35 ms	5408 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;

const int MXN = 1e5+5;

int tmp[MXN];
void move(int n, int p[]) {
    int mv = 0;
    for(int i=0; i<n; i++)
        if(p[i]<=n) {
            mv = (p[i]-1-i+n)%n;
            break;
        }
    for(int i=0; i<n; i++)
        tmp[(i+mv)%n] = p[i];
    for(int i=0; i<n; i++)
        p[i] = tmp[i];
}

int valid(int n, int inputSeq[]) {
    set<int> st;
    for(int i=0; i<n; i++) st.insert(inputSeq[i]);
    if(st.size()!=n) return 0;
    move(n, inputSeq);
    for(int i=0; i<n; i++)
        if(inputSeq[i]<=n && inputSeq[i]-1!=i)
            return 0;
    return 1;
}

int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
    move(n, gondolaSeq);
    vector<int> vec;
    for(int i=0; i<n; i++)
        if(gondolaSeq[i]>n)
            vec.push_back(i);
    if(vec.empty()) return 0;
    sort(vec.begin(), vec.end(), [&](int i, int j) {
        return gondolaSeq[i] < gondolaSeq[j];
    });
    vector<int> p(n);
    iota(p.begin(), p.end(), 1);
    int p1=0, p2=0;
    for(int i=n+1; i<=gondolaSeq[vec.back()]; i++) {
        replacementSeq[p2++] = p[vec[p1]];
        p[vec[p1]] = i;
        if(p[vec[p1]]==gondolaSeq[vec[p1]]) p1++;
    }
    return p2;
}

#define SZ(x) int(x.size())
const int MOD = 1e9+9;

inline int power(int a, int b) {
    int res = 1;
    while(b) {
        if(b&1) res = 1ll*res*a%MOD;
        a = 1ll*a*a%MOD;
        b >>= 1;
    }
    return res;
}

int countReplacement(int n, int inputSeq[]) {
    if(!valid(n, inputSeq)) return 0;
    vector<int> vec;
    for(int i=0; i<n; i++)
        if(inputSeq[i]>n)
            vec.push_back(i);
    sort(vec.begin(), vec.end(), [&](int i, int j) {
        return inputSeq[i] < inputSeq[j];
    });
    int p=n+1, ans = SZ(vec)==n ? n : 1;
    for(int i=0; i<SZ(vec); i++) {
        ans = 1ll*ans*power(SZ(vec)-i, inputSeq[vec[i]]-p)%MOD;
        p = inputSeq[vec[i]]+1;
    }
    return ans;
}

• 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