제출 #1280725

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1280725		karlsoos	곤돌라 (IOI14_gondola)	C++20	100 / 100	39 ms	6024 KiB

gondola

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

long long binpow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

int valid(int n, int inputSeq[]){
    bool seen[250001];
    fill_n(seen, 250001, 0);
    int anc = 0;
    for(int i = 0; i<n; i++){
        if(inputSeq[i] <= n){
            anc = i;
            break;
        }
    }  
    int canc = inputSeq[anc];
    for(int i = 0; i<n; i++){
        if(inputSeq[i] > n){
            if(seen[inputSeq[i]]){
                return 0;
            }
            seen[inputSeq[i]] = 1;
        }
        else{
            if(inputSeq[i] != canc){
                return 0;
            }
        }
        canc++;
        if(canc > n){
            canc -= n;
        }
    } 
    return 1;
}

int replacement(int n, int gondolaSeq[], int replacementSeq[]){
    int high[250001]; // position of high element if exists
    fill_n(high, 250001, -1);
    int anc = 0;
    for(int i = 0; i<n; i++){
        if(gondolaSeq[i] <= n){
            anc = i;
            break;
        }
    }
    
    for(int i = 0; i<n; i++){
        if(gondolaSeq[i] > n){
            high[gondolaSeq[i]] = i;
        }
    }
    int l = 0;
    int lasth = n;
    for(int i = n; i<250001; i++){
        if(high[i] != -1){
            //get initial value at high[i]
            int init = (high[i]+n)-anc;
            init += gondolaSeq[anc];
            while(init > n){
                init -= n;
            }
            replacementSeq[l] = init;
            l++;
            lasth++;
            while(lasth < i){
                replacementSeq[l] = lasth;
                l++;
                lasth++;
            }
        }

    }
    return l;
}

int countReplacement(int n, int inputSeq[]){
    // int high[1000000001]; // position of high element if exists
    // fill_n(high, 1000000001, -1);
    set<long long> high;
    long long bcount = 0;
    int ok = 1;
    int should = -1;
    for(int i = 0; i<n; i++){
        if(high.find(inputSeq[i]) != high.end()){
            ok = 0;

        }
        high.insert(inputSeq[i]);
        if(inputSeq[i] > n){
            bcount++;
        }
        else{
            if(should == -1){
                should = inputSeq[i];
            }
            else{
                if(inputSeq[i] != should){
                    ok = 0;
                }
            }
        }
        if(should != -1){
            should++;
            if(should > n){
                should -= n;
            }
        }
    }
    if(!ok) return ok;
    long long mod = 1000000009;
    long long ans = 1;
    if(bcount == n){    //NEW
        ans *= n;   //NEW
    }   //NEW
    int last = n;
    for(auto v : high){
        if(v <= n) continue;
        long long pow = v-last-1;
        ans = (ans*binpow(bcount, pow, mod))%mod;
        last = v;
        bcount--;
    }
    // for(int i = n+1; i<250001; i++){
    //     if(high[i] == -1){
    //         ans = (ans*(max((long long)1, bcount)))%mod;
    //     }
    //     else{
    //         bcount--;
    //     }
    // }
    return (int)ans;
}

// int main(){
//     int t;
//     cin>>t;
//     if(t > 6){
//         int n;
//         cin>>n;
//         int v[n];
//         for(int i = 0; i<n; i++){
//             cin>>v[i];
//         }
//         int l = countReplacement(n, v);
//         cout<<l<<"\n";
//     }
// }

• 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