Submission #1073275

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073275		Ludissey	Gondola (IOI14_gondola)	C++17	100 / 100	17 ms	4656 KiB

gondola

#include <bits/stdc++.h>
#include "gondola.h"
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()

using namespace std;

const int mod=1e9+9;
int MOD(int x){
    return (x+mod)%mod;
}

int fast_pow(int n, int p){
    if(p==1) return MOD(n);
    else if(p==0) return 1;
    else if(p%2==0){
        int u=fast_pow(n,p/2);
        return MOD(u*u);
    }else{
        return MOD(fast_pow(n,p-1)*n);
    }
}

signed valid(signed n, signed inputSeq[]){
    vector<int> a;
    for (int i = 0; i < n; i++)
    {
        if(inputSeq[i]<=n) a.push_back(inputSeq[i]);
    }
    int c=0;
    for (int i = 0; i < sz(a); i++)
    {
        if(i==0){ if(a[sz(a)-1]==a[i]-1) { c++; } }
        else if(a[i-1]==a[i]-1) c++;
    }
    return (c==n-1);
}




signed replacement(signed n, signed gondolaSeq[], signed replacementSeq[]){
    vector<pair<int,int>> a;
    vector<int> orig(n);
    pair<int,int> origNUMB={-1,-1};
    for (int i = 0; i < n; i++) { if(gondolaSeq[i]<=n) { origNUMB={i,gondolaSeq[i]-1}; break; } }
    int dep=0;
    if(origNUMB.first>=0){
        if(origNUMB.first<origNUMB.second) dep=origNUMB.second-origNUMB.first;
        else dep=origNUMB.second+(n-origNUMB.first);
    }
    for (int i = 0; i < n; i++)
    {
        if(origNUMB.first<0) orig[i]=i+1;
        else orig[i]=((i+dep)%n)+1;

    }
    for (int i = 0; i < n; i++)
    {
        if(gondolaSeq[i]>n) a.push_back({gondolaSeq[i],orig[i]});
    }
    if(sz(a)==0) return 0;
    sort(all(a));
    vector<int> toa;
    int lst=n;
    for (int i = 0; i < sz(a); i++)
    {
        lst++;
        int rem=(a[i].first-lst)-1;
        toa.push_back(a[i].second);
        while(rem>=0){
            toa.push_back(lst);
            lst++;
            rem--;
        }
    }
    for (int i = 0; i < sz(toa); i++) {
        replacementSeq[i]=toa[i];
    }
    return (int)(a.back().first-n);
}
signed countReplacement(signed n, signed inputSeq[]){
    vector<pair<int,int>> a;
    vector<int> orig(n);
    pair<int,int> origNUMB={-1,-1};
    for (int i = 0; i < n; i++) { if(inputSeq[i]<=n) { origNUMB={i,inputSeq[i]-1}; break; } }
    int dep=0;
    if(origNUMB.first>=0){
        if(origNUMB.first<origNUMB.second) dep=origNUMB.second-origNUMB.first;
        else dep=origNUMB.second+(n-origNUMB.first);
    }
    for (int i = 0; i < n; i++)
    {
        if(origNUMB.first<0) orig[i]=i+1;
        else orig[i]=((i+dep)%n)+1;
    }
    bool inv=false;
    for (int i = 0; i < n; i++){
        if(inputSeq[i]<=n&&inputSeq[i]!=orig[i]) { inv=true; break; }
    }
    if(inv) return 0;
    for (int i = 0; i < n; i++)
    {
        if(inputSeq[i]>n) a.push_back({inputSeq[i],orig[i]});
    }
    if(sz(a)==0) return 1;
    sort(all(a));
    int sm=1;
    int lst=n+1;
    for (int i = 0; i < sz(a); i++)
    {
        sm=MOD(sm*fast_pow(sz(a)-i,(a[i].first-lst)));
        lst=a[i].first+1;
    }
    int ex=1;
    if(origNUMB.first<0){
        sm=MOD(sm*n);
    }
    return (int)MOD(sm);
}

Compilation message (stderr)

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:116:9: warning: unused variable 'ex' [-Wunused-variable]
  116 |     int ex=1;
      |         ^~

• 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