Submission #153281

#	Time	Username	Problem	Language	Result	Execution time	Memory
153281		arnold518	Gondola (IOI14_gondola)	C++14	100 / 100	37 ms	2552 KiB

gondola

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;
const ll MOD = 1e9+9;

int valid(int N, int *A)
{
    int i, j;

    vector<int> S(A, A+N);
    sort(S.begin(), S.end());
    S.erase(unique(S.begin(), S.end()), S.end());
    if(S.size()!=N) return 0;

    int flag=-1;
    for(i=0; i<N; i++)
    {
        if(A[i]>N) continue;
        int t=(A[i]-1-i+N)%N;
        if(flag==-1) flag=t;
        else if(flag!=t) return 0;
    }
    return 1;
}

int replacement(int N, int *A, int *B)
{
    int i, j, ret=0;

    int flag=0;
    vector<pii> V;
    for(i=0; i<N; i++)
    {
        if(A[i]<=N)
        {
            flag=(A[i]-1-i+N)%N;
            continue;
        }
        V.push_back({A[i], i});
    }
    for(i=0; i<N; i++) A[i]=(i+flag)%N+1;
    sort(V.begin(), V.end());

    int now=N+1;
    for(i=0; i<V.size(); i++)
    {
        int p=V[i].first, q=V[i].second;
        while(A[q]!=p)
        {
            B[ret++]=A[q];
            A[q]=now++;
        }
    }
    return ret;
}

ll mypow(ll x, ll y)
{
    if(y==0) return 1;
    if(y%2) return mypow(x, y-1)*x%MOD;
    ll ret=mypow(x, y/2);
    return ret*ret%MOD;
}

int countReplacement(int N, int *A)
{
    int i, j; ll ans=1;
    if(!valid(N, A)) return 0;

    int flag=-1;
    vector<int> V; V.push_back(N);
    for(i=0; i<N; i++)
    {
        if(A[i]<=N) flag=0;
        else V.push_back(A[i]);
    }
    sort(V.begin(), V.end());
    for(i=1; i<V.size(); i++) ans=ans*mypow(V.size()-i, V[i]-V[i-1]-1)%MOD;
    if(flag==-1) ans=ans*N%MOD;
    return ans;
}

Compilation message (stderr)

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:19:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(S.size()!=N) return 0;
        ~~~~~~~~^~~
gondola.cpp:14:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:51:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<V.size(); i++)
              ~^~~~~~~~~
gondola.cpp:34:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j, ret=0;
            ^
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:84:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=1; i<V.size(); i++) ans=ans*mypow(V.size()-i, V[i]-V[i-1]-1)%MOD;
              ~^~~~~~~~~
gondola.cpp:73:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j; ll ans=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