Submission #12708

#	Time	Username	Problem	Language	Result	Execution time	Memory
12708		qja0950	Gondola (IOI14_gondola)	C++98	100 / 100	80 ms	9888 KiB

gondola

#include "gondola.h"
#include <algorithm>
#include <set>

using namespace std;

#define MAX_N 101101
#define MAX_V 250052
#define MOD 1000000009
typedef long long ll;


int CheckV[MAX_V];

int valid(int n, int inputSeq[])
{
    for(int i=0; i<n; i++) {
        int now = inputSeq[i];
        CheckV[now]++;
        if(CheckV[now] > 1) return 0;
    }
    
    int first = -1;
    for(int i=0; i<n; i++) {
        int now = inputSeq[i];
        if(now > n) continue;
        first = i;
        break;
    }
    if(first == -1) return 1;
    
    
    for(int i=0; i<n; i++) {
        int index = (first + i) % n;
        int value = (inputSeq[first] + i - 1) % n + 1;
        
        int now = inputSeq[index];
        if(now > n) continue;
        if(now != value) return 0;
    }
    return 1;
}

//----------------------

struct SORTR{
    int index;
    int value;
}SortR[MAX_N];
bool operator<(SORTR X, SORTR Y) {
    return X.value < Y.value;
}

int State[MAX_N];


int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    int first = 0;
    for(int i=0; i<n; i++) {
        int now = gondolaSeq[i];
        if(now > n) continue;
        first = i;
        break;
    }
    for(int i=0; i<n; i++) {
        int index = (first + i) % n;
        int value = (gondolaSeq[first] + i - 1) % n + 1;
        State[index] = value;
        
        SortR[i].index = i;
        SortR[i].value = gondolaSeq[i];
    }
    sort(SortR, SortR+n);
    
    int cnt = 0;
    int now = n;
    for(int i=0; i<n; i++) {
        int nowindex = SortR[i].index;
        int nowvalue = SortR[i].value;
        if(nowvalue < n) continue;
        while(State[nowindex] != nowvalue) {
            replacementSeq[cnt++] = State[nowindex];
            State[nowindex] = ++now;
        }
    }
    return cnt;
}
//----------------------


set<int> CheckSame;
ll Ans = 1;

struct SORTC{
    int index;
    int value;
}SortC[MAX_N];
bool operator<(SORTC X, SORTC Y) {
    return X.value < Y.value;
}

ll GetPower(int x, int k) {
    ll result = 1;
    ll powerx = x;
    while(k) {
        if(k%2 == 1) {
            result *= powerx;
            result %= MOD;
        }
        powerx *= powerx;
        powerx %= MOD;
        
        k/=2;
    }
    return result;
}

int countReplacement(int n, int inputSeq[])
{
    for(int i=0; i<n; i++) {
        int now = inputSeq[i];
        if(CheckSame.find(now) != CheckSame.end())
            return 0;
        CheckSame.insert(now);
    }
    int first = -1;
    for(int i=0; i<n; i++) {
        int now = inputSeq[i];
        if(now > n) continue;
        first = i;
        break;
    }
    if(first == -1) {
        Ans = n;
        first = 0;
    }
    for(int i=0; i<n; i++) {
        SortC[i].index = i;
        SortC[i].value = inputSeq[i];
    }
    sort(SortC, SortC+n);
    
    int last = n;
    for(int i=0; i<n; i++) {
        int nowvalue = SortC[i].value;
        if(nowvalue < n) continue;
        int count = n - i;
        Ans *= GetPower(count, nowvalue - last - 1);
        Ans %= MOD;
        
        last = nowvalue;
    }


    return (int)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