Submission #379825

#	Time	Username	Problem	Language	Result	Execution time	Memory
379825		ponytail	Gondola (IOI14_gondola)	C++17	Compilation error	0 ms	0 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;
}
int valid(long long n,long long 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(long long n,long long gondolaSeq[],long long 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]);
    }
    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(long long n,long long 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(long long n,long long 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=1;
        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;
    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(long long int, long long int*)':
gondola.cpp:19:16: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   19 |     if(s.size()!=n) return 0;
      |        ~~~~~~~~^~~
gondola.cpp: In function 'int chk_special_case(long long int, long long int*)':
gondola.cpp:87:18: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   87 |     if(all.size()!=n) return 0;
      |        ~~~~~~~~~~^~~
gondola.cpp: In function 'int valid(long long int, long long int*)':
gondola.cpp:16:19: warning: control reaches end of non-void function [-Wreturn-type]
   16 |     set<long long>s;
      |                   ^
/tmp/ccur8eTI.o: In function `main':
grader.cpp:(.text.startup+0xb6): undefined reference to `valid'
grader.cpp:(.text.startup+0x108): undefined reference to `countReplacement'
grader.cpp:(.text.startup+0x132): undefined reference to `replacement'
collect2: error: ld returned 1 exit status