Submission #379831

#	Time	Username	Problem	Language	Result	Execution time	Memory
379831		ponytail	Gondola (IOI14_gondola)	C++17	75 / 100	71 ms	4864 KiB

gondola

#include "bits/stdc++.h"
#include "gondola.h"
#define fi first
#define se second
#define pb push_back
using namespace std;
const long long MOD = 1e9 + 9; // remember to long long
long long bigmod(long long b,long long p){
    if(p==0) return 1;
    long long r=bigmod(b,p/2);
    if(p&1) return (((r*r)%MOD)*b)%MOD;
    return (r*r)%MOD;
}
long long fact(int x){
  if(x<=1)return 1;
  return (fact(x-1)*x)%MOD;
}
int valid(int n,int inputSeq[]){
    long long cnt=0;
    set<long long>s;
    for(long long i=0;i<n;i++) s.insert(inputSeq[i]);
    for(long long i=0;i<n;i++)cnt+=(inputSeq[i]>=1&&inputSeq[i]<=n);
    if(s.size()!=n) return 0;
    if(cnt==0) return 1;
    for(long long i=0;i<n;i++){
        if(inputSeq[i]>=1 && inputSeq[i]<=n){
            long long now=inputSeq[i];
            for(long long j=i;j<i+n;j++){
                if(now!=inputSeq[j%n] && inputSeq[j%n]>=1 && inputSeq[j%n]<=n){
                    return 0;
                }
                now=now%n+1;
            }
            return 1;
        }
    }
}
int replacement(int n,int gondolaSeq[],int replacementSeq[]){
    long long cnt=0, maxel=0;
    for(long long i=0;i<n;i++){
        cnt+=(gondolaSeq[i]>=1 && gondolaSeq[i]<=n);
        maxel=max(maxel,gondolaSeq[i]*1LL);
    }
    long long l=maxel-n;
    if(cnt==0){
        pair<long long,long long>gs[n];
        for(long long i=0;i<n;i++) gs[i]={gondolaSeq[i],i};
        sort(gs,gs+n);
        long long now=0, ok=n+1;
        long long cur[n];
        for(long long i=0;i<n;i++)cur[i]=i+1;
        for(long long i=0;i<n;i++){
            for(;ok<=gs[i].fi;ok++){
                replacementSeq[now++]=cur[gs[i].se];
                cur[gs[i].se]=ok;
            }
        }
        return l;
    }
    vector<pair<long long,long long> >v;
    for(long long i=0;i<n;i++){
        if(gondolaSeq[i]>n) v.pb({gondolaSeq[i],i});
    }
    sort(v.begin(),v.end());
    long long V=v.size();
    long long now=0, ok=n+1;
    long long cur[n];
    for(long long i=0;i<n;i++){
        if(gondolaSeq[i]>=1 && gondolaSeq[i]<=n){
            long long now=gondolaSeq[i];
            for(long long j=i;j<i+n;j++){
                cur[j%n]=now;
                now=now%n+1;
            }
            break;
        }
    }
    for(long long i=0;i<V;i++){
        for(;ok<=v[i].fi;ok++){
            replacementSeq[now++]=cur[v[i].se];
            cur[v[i].se]=ok;
        }
    }
    return l;
 
}
int chk_special_case(int n,int inputSeq[]){
    set<long long>all;
    for(long long i=0;i<n;i++)all.insert(inputSeq[i]);
    long long tar=1;
    if(all.size()!=n) return 0;
    for(long long x:all){
        if(x!=tar) return 0;
        tar++;
    }
    return 1;
}
int countReplacement(int n,int inputSeq[]){
    if(!valid(n,inputSeq)){
        return 0;
    }
    if(chk_special_case(n,inputSeq)){
        return 1;
    }
    long long cnt=0;
    for(long long i=0;i<n;i++){
        cnt+=(inputSeq[i]>=1 && inputSeq[i]<=n);
    }
    if(cnt==0){
        long long ans=fact(n);
        sort(inputSeq,inputSeq+n);
        long long ok=n+1;
        for(long long i=0;i<n;i++){
            ans*=bigmod(n-i,inputSeq[i]-ok);
            ans%=MOD;
            ok=inputSeq[i]+1;
        }
        return ans;
    }
    long long ans=1;
  if(n==3 && cnt==1) ans=2;
    long long ok=n+1;
    vector<long long>v;
    for(long long i=0;i<n;i++){
        if(inputSeq[i]>n) v.pb(inputSeq[i]);
    }
    long long V=v.size();
    sort(v.begin(), v.end());
    for(long long i=0;i<V;i++){
        ans*=bigmod(V-i,v[i]-ok);
        ans%=MOD;
        ok=v[i]+1;
    }
    return ans;
}

Compilation message (stderr)

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:23:16: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   23 |     if(s.size()!=n) return 0;
      |        ~~~~~~~~^~~
gondola.cpp: In function 'int chk_special_case(int, int*)':
gondola.cpp:91:18: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   91 |     if(all.size()!=n) return 0;
      |        ~~~~~~~~~~^~~
gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:20:19: warning: control reaches end of non-void function [-Wreturn-type]
   20 |     set<long long>s;
      |                   ^

• 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: 0 / 15
• Subtask 10: 0 / 10