Submission #379820

#	Time	Username	Problem	Language	Result	Execution time	Memory
379820		ponytail	Gondola (IOI14_gondola)	C++17	55 / 100	40 ms	4716 KiB

gondola

#include "bits/stdc++.h"
#include "gondola.h"
#define fi first
#define se second
#define pb push_back
using namespace std;
const int MOD = 1e9 + 9; // remember to long long
int valid(int n,int inputSeq[]){
    int cnt=0;
    set<int>s;
    for(int i=0;i<n;i++) s.insert(inputSeq[i]);
    for(int i=0;i<n;i++)cnt+=(inputSeq[i]>=1&&inputSeq[i]<=n);
    if(s.size()!=n) return 0;
    if(cnt==0) return 1;
    for(int i=0;i<n;i++){
        if(inputSeq[i]>=1 && inputSeq[i]<=n){
            int now=inputSeq[i];
            for(int 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[]){
    int cnt=0, maxel=0;
    for(int i=0;i<n;i++){
        cnt+=(gondolaSeq[i]>=1 && gondolaSeq[i]<=n);
        maxel=max(maxel,gondolaSeq[i]);
    }
    int l=maxel-n;
    if(cnt==0){
        pair<int,int>gs[n];
        for(int i=0;i<n;i++) gs[i]={gondolaSeq[i],i};
        sort(gs,gs+n);
        int now=0, ok=n+1;
        int cur[n];
        for(int i=0;i<n;i++)cur[i]=i+1;
        for(int 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<int,int> >v;
    for(int i=0;i<n;i++){
        if(gondolaSeq[i]>n) v.pb({gondolaSeq[i],i});
    }
    sort(v.begin(),v.end());
    int V=v.size();
    int now=0, ok=n+1;
    int cur[n];
    for(int i=0;i<n;i++){
        if(gondolaSeq[i]>=1 && gondolaSeq[i]<=n){
            int now=gondolaSeq[i];
            for(int j=i;j<i+n;j++){
                cur[j%n]=now;
                now=now%n+1;
            }
            break;
        }
    }
    for(int 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 countReplacement(int n,int inputSeq[]){

}

Compilation message (stderr)

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:13:16: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   13 |     if(s.size()!=n) return 0;
      |        ~~~~~~~~^~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:79:1: warning: no return statement in function returning non-void [-Wreturn-type]
   79 | }
      | ^
gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:10:13: warning: control reaches end of non-void function [-Wreturn-type]
   10 |     set<int>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: 0 / 5
• Subtask 8: 0 / 15
• Subtask 9: 0 / 15
• Subtask 10: 0 / 10