oj.uz

Submission #379832

# Submission time Handle Problem Language Result Execution time Memory
379832 2021-03-19T12:43:45 Z ponytail Gondola (IOI14_gondola) C++17
100 / 100
 100 ms 6252 KB 
#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=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;
    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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 12 ms 2412 KB Output is correct
7 Correct 30 ms 3692 KB Output is correct
8 Correct 24 ms 3948 KB Output is correct
9 Correct 7 ms 1516 KB Output is correct
10 Correct 30 ms 4588 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 12 ms 2284 KB Output is correct
7 Correct 30 ms 3692 KB Output is correct
8 Correct 25 ms 3948 KB Output is correct
9 Correct 7 ms 1644 KB Output is correct
10 Correct 27 ms 4588 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 0 ms 364 KB Output is correct
13 Correct 16 ms 2156 KB Output is correct
14 Correct 0 ms 364 KB Output is correct
15 Correct 38 ms 4716 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 0 ms 364 KB Output is correct
7 Correct 1 ms 380 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 0 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 10 ms 1260 KB Output is correct
12 Correct 13 ms 1388 KB Output is correct
13 Correct 17 ms 1636 KB Output is correct
14 Correct 10 ms 1260 KB Output is correct
15 Correct 26 ms 2396 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 0 ms 364 KB Output is correct
7 Correct 0 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 67 ms 4076 KB Output is correct
10 Correct 48 ms 3436 KB Output is correct
11 Correct 20 ms 1516 KB Output is correct
12 Correct 23 ms 1772 KB Output is correct
13 Correct 5 ms 620 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 61 ms 4076 KB Output is correct
10 Correct 48 ms 3436 KB Output is correct
11 Correct 17 ms 1516 KB Output is correct
12 Correct 21 ms 1772 KB Output is correct
13 Correct 5 ms 620 KB Output is correct
14 Correct 88 ms 5484 KB Output is correct
15 Correct 100 ms 6252 KB Output is correct
16 Correct 14 ms 1388 KB Output is correct
17 Correct 57 ms 4204 KB Output is correct
18 Correct 30 ms 2540 KB Output is correct