oj.uz

Submission #1010513

# Submission time Handle Problem Language Result Execution time Memory
1010513 2024-06-29T07:29:49 Z Mardonbekhazratov Gondola (IOI14_gondola) C++17
75 / 100
 49 ms 7760 KB 
#include "gondola.h"
#include<bits/stdc++.h>

using namespace std;

int valid(int n, int inputSeq[]){
    int mn=n,id=-1;
    map<int,int>cnt;
    for(int i=0;i<n;i++){
        cnt[inputSeq[i]]++;
        if(inputSeq[i]<=mn){
            mn=inputSeq[i];
            id=i;
        }
    }
    for(auto [x,y]:cnt){
        if(y>1) return 0;
    }
    if(mn==n) return 1;
    id=(id-mn+1+n)%n;
    for(int i=0;i<n;i++){
        if(inputSeq[(id+i)%n]==i+1 || inputSeq[(id+i)%n]>n) continue;
        return 0;
    }
    return 1;
}

//----------------------


int replacement(int n, int gondolaSeq[], int replacementSeq[]){
    const int N=2.5e5;
    vector<int>cnt(N+1,0);
    int mn=N,id=0,mx=0;
    set<int>s;
    set<pair<int,int>>t;
    for(int i=0;i<n;i++){
        cnt[gondolaSeq[i]]++;
        if(gondolaSeq[i]<mn){
            mn=gondolaSeq[i];
            id=i;
        }
        mx=max(mx,gondolaSeq[i]);
        if(gondolaSeq[i]<=n) s.insert(gondolaSeq[i]);
        else t.insert({gondolaSeq[i],i});
    }
    if(mn<=n){
        id=(id-mn+1+n)%n;
    }
    int ans=0,last=n+1;
    for(auto [x,y]:t){
        int k=(y-id+n)%n;
        replacementSeq[ans++]=k+1;
        for(int j=last;j<x;j++) replacementSeq[ans++]=j;
        last=x+1;
    }
    return ans;
}

//----------------------

int countReplacement(int n, int inputSeq[]){
    const int MOD=1e9+9;
    if(!valid(n,inputSeq)){
        return 0;
    }
    int c=0;
    vector<int>cnt((int)2.5e5+2,0);
    int mx=0;
    for(int i=0;i<n;i++){
        if(inputSeq[i]>n) c++;
        cnt[inputSeq[i]]++;
        mx=max(inputSeq[i],mx);
    }
    int replacementSeq[(int)3e5];
    int l=replacement(n,inputSeq,replacementSeq);
    int ans=1;
    for(int i=n+1;i<=mx;i++){
        if(cnt[i]) c--;
        else ans=1LL*ans*c%MOD;
    }
    return ans;
}

Compilation message

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:76:9: warning: unused variable 'l' [-Wunused-variable]
   76 |     int l=replacement(n,inputSeq,replacementSeq);
      |         ^

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 7 ms 2396 KB Output is correct
7 Correct 17 ms 4188 KB Output is correct
8 Correct 12 ms 4444 KB Output is correct
9 Correct 4 ms 1624 KB Output is correct
10 Correct 16 ms 4944 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 7 ms 2528 KB Output is correct
7 Correct 20 ms 4168 KB Output is correct
8 Correct 14 ms 4444 KB Output is correct
9 Correct 4 ms 1628 KB Output is correct
10 Correct 17 ms 4976 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 11 ms 2344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 27 ms 5308 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1372 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 1 ms 1372 KB Output is correct
4 Correct 1 ms 1372 KB Output is correct
5 Correct 1 ms 1372 KB Output is correct
6 Correct 1 ms 1372 KB Output is correct
7 Correct 1 ms 1372 KB Output is correct
8 Correct 1 ms 1372 KB Output is correct
9 Correct 1 ms 1372 KB Output is correct
10 Correct 1 ms 1372 KB Output is correct
11 Correct 14 ms 5724 KB Output is correct
12 Correct 20 ms 6392 KB Output is correct
13 Correct 15 ms 3632 KB Output is correct
14 Correct 15 ms 5724 KB Output is correct
15 Correct 17 ms 3164 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3420 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 2 ms 3488 KB Output is correct
4 Correct 2 ms 3420 KB Output is correct
5 Correct 2 ms 3420 KB Output is correct
6 Correct 1 ms 3420 KB Output is correct
7 Correct 1 ms 3544 KB Output is correct
8 Correct 1 ms 3420 KB Output is correct
9 Correct 49 ms 7760 KB Output is correct
10 Correct 33 ms 7004 KB Output is correct
11 Correct 14 ms 4700 KB Output is correct
12 Correct 14 ms 5100 KB Output is correct
13 Incorrect 5 ms 3932 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3672 KB Output is correct
2 Correct 2 ms 3420 KB Output is correct
3 Correct 2 ms 3420 KB Output is correct
4 Correct 2 ms 3420 KB Output is correct
5 Correct 2 ms 3420 KB Output is correct
6 Correct 1 ms 3416 KB Output is correct
7 Correct 2 ms 3420 KB Output is correct
8 Correct 1 ms 3420 KB Output is correct
9 Correct 40 ms 7624 KB Output is correct
10 Correct 33 ms 7000 KB Output is correct
11 Correct 14 ms 4700 KB Output is correct
12 Correct 16 ms 4956 KB Output is correct
13 Incorrect 5 ms 3784 KB Output isn't correct
14 Halted 0 ms 0 KB -