oj.uz

Submission #316985

# Submission time Handle Problem Language Result Execution time Memory
316985 2020-10-28T20:27:13 Z neki Gondola (IOI14_gondola) C++14
100 / 100
 81 ms 8556 KB 
#include <bits/stdc++.h>
#include <gondola.h>
#define loop(i, a, b) for(long long i=a;i<b;i++)
#define pool(i, a, b) for(long long i=a-1;i>=b;i--)
#define fore(i, a) for(auto&& i:a)
#define fi first
#define se second
#define ps(a) push_back(a)
#define pb(a) pop_back(a)
#define sc scanf
#define vc vector
#define pa pair<ll, ll>
#define ll long long
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(), a.end()
#define llmax LLONG_MAX/2
#define llmin -LLONG_MAX/2
using namespace std;
#define mn 200100
#define pa pair<ll, ll>
#define ld long double 
#define k 450

int valid(int n, int inputSeq[]){
    vc<pa> tes;
    map<ll, ll> cnt;loop(i, 0, n) cnt[inputSeq[i]]++;
    fore(v, cnt) if(v.se>1) return 0;
    loop(i, 0, n) if(inputSeq[i]<=n)tes.ps(make_pair(i, inputSeq[i]));
    if(tes.size()==0) return 1;
    ll siz=tes.size();
    loop(i, 0, tes.size()) if((tes[(i+1)%siz].fi-tes[i].fi+n)%n!=(tes[(i+1)%siz].se-tes[i%siz].se+n)%n){
        return 0;
    }
    
    return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]){
    ll zac=1, cnt=0;
    map<ll, ll> poi;
    loop(i, 0, n){ 
        if(gondolaSeq[i]<=n) zac=(gondolaSeq[i]-i+n)%n;
        else poi[gondolaSeq[i]]=i;
    }
    if(poi.size()==0) return 0;
    vc<ll> cur(n, 0);
    loop(i, 0, n){
        cur[i]=(zac+i)%n;
        if(cur[i]==0) cur[i]=n;
    }
    loop(j, n+1, poi.begin()->fi+1) replacementSeq[cnt++]=cur[poi.begin()->se], cur[poi.begin()->se]=j;
    for(auto v=poi.begin();v!=poi.end();++v){
        auto ne=v; ++ne;
        if(ne==poi.end()) break;
        loop(j, v->fi+1, ne->fi+1) replacementSeq[cnt++]=cur[ne->se], cur[ne->se]=j;
    }
    auto bac=poi.end();bac--;
    return cnt;
}
ll mod=1000000009;
ll pot(ll ba, ll ex){
    ba%=mod;
    ll ret=1;
    while(ex){
        if(ex&1) ret*=ba;
        ba*=ba;
        ex/=2;
        ret%=mod;
        ba%=mod;
    }
    return ret;
}
int countReplacement(int n, int inputSeq[]){
    if(!valid(n, inputSeq)) return 0;
    ll ans=1;
    vc<ll> srt;
    loop(i, 0, n) if(inputSeq[i]>n) srt.ps(inputSeq[i]);
    if(srt.size()==0) return 1;
    srt.ps(n);
    sort(all(srt));
    loop(i, 0, srt.size())srt[i]-=n+i;
    ll siz=(ll)srt.size();
    loop(i, 1, (ll)srt.size()){
        if(srt[i]-srt[i-1]) ans*=pot(siz-i, srt[i]-srt[i-1]);
        ans%=mod;
    }
    if(srt.size()==n+1) ans*=n;
    return ans%mod;
}

Compilation message

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:3:42: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define loop(i, a, b) for(long long i=a;i<b;i++)
......
   32 |     loop(i, 0, tes.size()) if((tes[(i+1)%siz].fi-tes[i].fi+n)%n!=(tes[(i+1)%siz].se-tes[i%siz].se+n)%n){
      |          ~~~~~~~~~~~~~~~~                 
gondola.cpp:32:5: note: in expansion of macro 'loop'
   32 |     loop(i, 0, tes.size()) if((tes[(i+1)%siz].fi-tes[i].fi+n)%n!=(tes[(i+1)%siz].se-tes[i%siz].se+n)%n){
      |     ^~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:3:42: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define loop(i, a, b) for(long long i=a;i<b;i++)
......
   81 |     loop(i, 0, srt.size())srt[i]-=n+i;
      |          ~~~~~~~~~~~~~~~~                 
gondola.cpp:81:5: note: in expansion of macro 'loop'
   81 |     loop(i, 0, srt.size())srt[i]-=n+i;
      |     ^~~~
gondola.cpp:87:18: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   87 |     if(srt.size()==n+1) ans*=n;
      |        ~~~~~~~~~~^~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 16 ms 4220 KB Output is correct
7 Correct 35 ms 5248 KB Output is correct
8 Correct 33 ms 7800 KB Output is correct
9 Correct 9 ms 2560 KB Output is correct
10 Correct 35 ms 8556 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 16 ms 4252 KB Output is correct
7 Correct 33 ms 5248 KB Output is correct
8 Correct 32 ms 7672 KB Output is correct
9 Correct 9 ms 2688 KB Output is correct
10 Correct 37 ms 8556 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 18 ms 2944 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 50 ms 7668 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 11 ms 1024 KB Output is correct
12 Correct 12 ms 1152 KB Output is correct
13 Correct 25 ms 3304 KB Output is correct
14 Correct 11 ms 1024 KB Output is correct
15 Correct 28 ms 3304 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 376 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 51 ms 6008 KB Output is correct
10 Correct 40 ms 5368 KB Output is correct
11 Correct 14 ms 1920 KB Output is correct
12 Correct 17 ms 2304 KB Output is correct
13 Correct 4 ms 768 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 57 ms 6008 KB Output is correct
10 Correct 38 ms 5368 KB Output is correct
11 Correct 14 ms 1920 KB Output is correct
12 Correct 17 ms 2360 KB Output is correct
13 Correct 5 ms 768 KB Output is correct
14 Correct 76 ms 6648 KB Output is correct
15 Correct 81 ms 7544 KB Output is correct
16 Correct 11 ms 1664 KB Output is correct
17 Correct 44 ms 5112 KB Output is correct
18 Correct 24 ms 3072 KB Output is correct