Submission #7316

#	Time	Username	Problem	Language	Result	Execution time	Memory
7316		myungwoo	Gondola (IOI14_gondola)	C++98	100 / 100	48 ms	4556 KiB

gondola

#include <map>
#include <vector>
#include <algorithm>
#include "gondola.h"
using namespace std;
 
#define MAXN 100000
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
typedef long long lld;
 
static const int MOD = 1e9 + 9;
static int tmp[MAXN];
 
int valid(int n,int inputSeq[])
{
    int i,j,p = -1;
    for (i=0;i<n;i++){
        tmp[i] = inputSeq[i];
        if (inputSeq[i] <= n){
            j = (i-inputSeq[i]+1+n)%n;
            if (p < 0) p = j;
            else if (p != j) return 0;
        }
    }
    sort(tmp,tmp+n);
    for (i=1;i<n;i++) if (tmp[i-1] == tmp[i]) return 0;
    return 1;
}
 
int replacement(int n,int gondolaSeq[],int replacementSeq[])
{
    if (!valid(n,gondolaSeq)) return -1;
    int i,j,p = -1;
    for (i=0;i<n;i++){
        if (gondolaSeq[i] <= n){
            j = (i-gondolaSeq[i]+1+n)%n;
            if (p < 0) p = j;
            else if (p != j) return 0;
        }
    }
    int y=0;
    for (i=0;i<n;i++) if (gondolaSeq[i] > n){
        if (y < gondolaSeq[i]) y = gondolaSeq[i];
    }
    if (!y) return 0;
    map<int,int> pos;
    for (i=0;i<n;i++) pos[gondolaSeq[i]] = i;
    if (p == -1) p = 0;
    int c = 0, t = pos[y];
    for (i=0;i<n;i++) tmp[i] = (i-p+n)%n+1;
    for (i=n+1;i<=y;i++){
        int x = pos.count(i) ? pos[i] : t;
        replacementSeq[c++] = tmp[x];
        tmp[x] = i;
    }
    return y-n;
}
 
int pow(int a,int b)
{
    int ret = 1,t = a,i;
    for (i=0;i<31;i++,t=(lld)t*t%MOD) if (b&(1<<i)){
        ret = (lld)ret*t%MOD;
    }
    return ret;
}
 
int countReplacement(int n,int inputSeq[])
{
    if (!valid(n,inputSeq)) return 0;
    int ret = n,last = n,i;
    vector <int> a;
    for (i=0;i<n;i++){
        if (inputSeq[i] <= n) ret = 1;
        else a.pb(inputSeq[i]);
    }
    sort(all(a));
    int left = sz(a);
    for (i=0;i<sz(a);i++){
        int dummy = a[i] - last - 1;
        ret = ((lld)ret*pow(left,dummy))%MOD;
        last = a[i]; left--;
    }
    return ret;
}

• 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