Submission #197499

#	Time	Username	Problem	Language	Result	Execution time	Memory
197499		handlename	Gondola (IOI14_gondola)	C++17	100 / 100	58 ms	5380 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
int valid(int n, int inputSeq[]) {
    unordered_set<int> appeared;
    int value=-1;
    for (int i=0;i<n;i++){
        if (appeared.find(inputSeq[i])!=appeared.end()) return 0;
        appeared.insert(inputSeq[i]);
        if (inputSeq[i]>n) continue;
        if (value==-1) value=((inputSeq[i]-i)%n+n)%n;
        if (value<0) value+=n;
        else {
            int curval=((inputSeq[i]-i)%n);
            if (curval<0) curval+=n;
            if (curval!=value) return 0;
        }
    }
    return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
    int value=-1;
    vector<pair<int,int> > arr;
    int curnum=n+1,curpos=0;
    for (int i=0;i<n;i++){
        if (gondolaSeq[i]>n){
            arr.push_back(make_pair(gondolaSeq[i],i));
        }
        else value=((gondolaSeq[i]-i)%n+n)%n;
    }
    sort(arr.begin(),arr.end());
    for (int i=0;i<arr.size();i++){
        int endd=arr[i].first;
        int id=arr[i].second;
        int realid;
        if (value!=-1){
            realid=(value+id)%n;
        }
        else realid=id+1;
        if (realid==0) realid=n;
        replacementSeq[curpos]=realid;
        curpos++;
        while (curnum<endd){
            replacementSeq[curpos]=curnum;
            curnum++;
            curpos++;
        }
        curnum++;
        
    }
    return curpos;
}
long long m;
long long power(long long a,long long b){
    long long ans=1;
    a%=m;
    while (b>0){
        if (b%2==1) ans=(ans*a)%m;
        b/=2;
        a=(a*a)%m;
    }
    return ans;
}
int countReplacement(int n, int inputSeq[]) {
    if (valid(n,inputSeq)==0) return 0;
    m=1e9+9;
    int value=-1;
    vector<pair<int,int> > arr;
    for (int i=0;i<n;i++){
        if (inputSeq[i]>n){
            arr.push_back(make_pair(inputSeq[i],i));
        }
        else value=((inputSeq[i]-i)%n+n)%n;
    }
    sort(arr.begin(),arr.end());
    long long ans=1;
    if (value==-1) ans=n;
    int k=arr.size();
    int prevval=n+1;
    for (int i=0;i<arr.size();i++){
        int curval=arr[i].first;
        ans*=power(k-i,curval-prevval);
        ans%=m;
        prevval=curval+1;
    }
    return (int)ans;
}

Compilation message (stderr)

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:32:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<arr.size();i++){
                  ~^~~~~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:80:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<arr.size();i++){
                  ~^~~~~~~~~~~

• 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