Submission #118566

#	Time	Username	Problem	Language	Result	Execution time	Memory
118566		eohomegrownapps	Gondola (IOI14_gondola)	C++14	100 / 100	90 ms	8764 KiB

gondola

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

long long m=1000000009;

long long mexp(long long a, long long b){
    if (b==0){
        return 1;
    }
    if (b%2==0){
        long long sqr = mexp(a,b/2);
        return (sqr*sqr)%m;
    } else {
        return (mexp(a,b-1)*a)%m;
    }
}

int valid(int n, int inputSeq[]) {
    map<long long,bool> visited;
    long long first = -1;
    bool flag = false;
    for (long long i = 0; i<n; i++){
        if (visited[inputSeq[i]]){
            return 0;
        }
        visited[inputSeq[i]]=true;
        if (inputSeq[i]<=n&&flag==false){
            first=i;
            flag=true;
        }
    }
    if (first==-1){
        return 1;
    }
    long long pt = inputSeq[first];
    for (long long i = first; i<first+n; i++){
        long long im = i%n;
        if (inputSeq[im]!=pt&&inputSeq[im]<=n){
            return 0;
        }
        pt++;
        if (pt>n){
            pt=1;
        }
    }
    return 1;
}

int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
    long long first = -1;
    for (long long i = 0; i<n; i++){
        if (gondolaSeq[i]<=n){
            first=i;
            break;
        }
    }
    vector<pair<long long,long long> > gondolas;
    //first: new number; second actual number
    long long pt;
    if (first==-1){
        pt=1;
        first=0;
    } else {
        pt=gondolaSeq[first];
    }
    for (long long i = first; i<first+n; i++){
        long long im = i%n;
        if (gondolaSeq[im]>n){
            gondolas.push_back(make_pair(gondolaSeq[im],pt));
        }
        pt++;
        if (pt>n){
            pt=1;
        }
    }
    sort(gondolas.begin(),gondolas.end());
    long long point = 0;
    long long current = n+1; //index of gondola being replaced
    long long numgondolas = 0;
    vector<long long> newname(n+1);
    for (long long i = 0; i<=n; i++){
        newname[i]=i;
    }
    while (point<gondolas.size()){
        while (current<=gondolas[point].first){
            replacementSeq[numgondolas]=newname[gondolas[point].second];
            newname[gondolas[point].second]=current;
            numgondolas++;
            current++;
        }
        point++;
    }
    return numgondolas;
}

int countReplacement(int n, int inputSeq[]) {
    map<long long,bool> visited;
    long long first = -1;
    bool flag = false;
    bool small=true;
    for (long long i = 0; i<n; i++){
        if (visited[inputSeq[i]]){
            return 0;
        }
        visited[inputSeq[i]]=true;
        if (inputSeq[i]<=n&&flag==false){
            first=i;
            flag=true;
        }
        if (inputSeq[i]>n){
            small=false;
        }
    }
    if (small){
        return 1;
    }
    bool noneSmall = false;
    if (first==-1){
        noneSmall=true; //no gondolas <=n
    }
    
    vector<long long> gondolas;
    //first: new number; second actual number
    long long pt;
    if (first==-1){
        pt=1;
        first=0;
    } else {
        pt=inputSeq[first];
    }
    for (long long i = first; i<first+n; i++){
        long long im = i%n;
        if (inputSeq[im]!=pt&&inputSeq[im]<=n){
            return 0;
        }
        if (inputSeq[im]>n){
            gondolas.push_back(inputSeq[im]);
        }
        pt++;
        if (pt>n){
            pt=1;
        }
    }
    sort(gondolas.begin(),gondolas.end());
    long long total = 1;
    long long prev = n;
    long long numleft = gondolas.size();
    for (auto p : gondolas){
        total*=mexp(numleft,p-prev-1);
        total%=m;
        numleft--;
        prev=p;
    }
    if (noneSmall){
        total*=n;
        total%=m;
    }
    return total;
}

Compilation message (stderr)

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:85:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (point<gondolas.size()){
            ~~~~~^~~~~~~~~~~~~~~~

• 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