oj.uz

Submission #1073275

# Submission time Handle Problem Language Result Execution time Memory
1073275 2024-08-24T11:34:57 Z Ludissey Gondola (IOI14_gondola) C++17
100 / 100
 17 ms 4656 KB 
#include <bits/stdc++.h>
#include "gondola.h"
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()

using namespace std;

const int mod=1e9+9;
int MOD(int x){
    return (x+mod)%mod;
}

int fast_pow(int n, int p){
    if(p==1) return MOD(n);
    else if(p==0) return 1;
    else if(p%2==0){
        int u=fast_pow(n,p/2);
        return MOD(u*u);
    }else{
        return MOD(fast_pow(n,p-1)*n);
    }
}

signed valid(signed n, signed inputSeq[]){
    vector<int> a;
    for (int i = 0; i < n; i++)
    {
        if(inputSeq[i]<=n) a.push_back(inputSeq[i]);
    }
    int c=0;
    for (int i = 0; i < sz(a); i++)
    {
        if(i==0){ if(a[sz(a)-1]==a[i]-1) { c++; } }
        else if(a[i-1]==a[i]-1) c++;
    }
    return (c==n-1);
}




signed replacement(signed n, signed gondolaSeq[], signed replacementSeq[]){
    vector<pair<int,int>> a;
    vector<int> orig(n);
    pair<int,int> origNUMB={-1,-1};
    for (int i = 0; i < n; i++) { if(gondolaSeq[i]<=n) { origNUMB={i,gondolaSeq[i]-1}; break; } }
    int dep=0;
    if(origNUMB.first>=0){
        if(origNUMB.first<origNUMB.second) dep=origNUMB.second-origNUMB.first;
        else dep=origNUMB.second+(n-origNUMB.first);
    }
    for (int i = 0; i < n; i++)
    {
        if(origNUMB.first<0) orig[i]=i+1;
        else orig[i]=((i+dep)%n)+1;

    }
    for (int i = 0; i < n; i++)
    {
        if(gondolaSeq[i]>n) a.push_back({gondolaSeq[i],orig[i]});
    }
    if(sz(a)==0) return 0;
    sort(all(a));
    vector<int> toa;
    int lst=n;
    for (int i = 0; i < sz(a); i++)
    {
        lst++;
        int rem=(a[i].first-lst)-1;
        toa.push_back(a[i].second);
        while(rem>=0){
            toa.push_back(lst);
            lst++;
            rem--;
        }
    }
    for (int i = 0; i < sz(toa); i++) {
        replacementSeq[i]=toa[i];
    }
    return (int)(a.back().first-n);
}
signed countReplacement(signed n, signed inputSeq[]){
    vector<pair<int,int>> a;
    vector<int> orig(n);
    pair<int,int> origNUMB={-1,-1};
    for (int i = 0; i < n; i++) { if(inputSeq[i]<=n) { origNUMB={i,inputSeq[i]-1}; break; } }
    int dep=0;
    if(origNUMB.first>=0){
        if(origNUMB.first<origNUMB.second) dep=origNUMB.second-origNUMB.first;
        else dep=origNUMB.second+(n-origNUMB.first);
    }
    for (int i = 0; i < n; i++)
    {
        if(origNUMB.first<0) orig[i]=i+1;
        else orig[i]=((i+dep)%n)+1;
    }
    bool inv=false;
    for (int i = 0; i < n; i++){
        if(inputSeq[i]<=n&&inputSeq[i]!=orig[i]) { inv=true; break; }
    }
    if(inv) return 0;
    for (int i = 0; i < n; i++)
    {
        if(inputSeq[i]>n) a.push_back({inputSeq[i],orig[i]});
    }
    if(sz(a)==0) return 1;
    sort(all(a));
    int sm=1;
    int lst=n+1;
    for (int i = 0; i < sz(a); i++)
    {
        sm=MOD(sm*fast_pow(sz(a)-i,(a[i].first-lst)));
        lst=a[i].first+1;
    }
    int ex=1;
    if(origNUMB.first<0){
        sm=MOD(sm*n);
    }
    return (int)MOD(sm);
}

Compilation message

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:116:9: warning: unused variable 'ex' [-Wunused-variable]
  116 |     int ex=1;
      |         ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 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 0 ms 344 KB Output is correct
6 Correct 3 ms 1496 KB Output is correct
7 Correct 6 ms 2260 KB Output is correct
8 Correct 6 ms 2260 KB Output is correct
9 Correct 2 ms 948 KB Output is correct
10 Correct 6 ms 2260 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 ms 348 KB Output is correct
6 Correct 3 ms 1460 KB Output is correct
7 Correct 7 ms 2260 KB Output is correct
8 Correct 6 ms 2260 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 6 ms 2260 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 3 ms 768 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 7 ms 1824 KB Output is correct

Subtask #4
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 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #5
10.0 / 10.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 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #6
20.0 / 20.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 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 6 ms 1628 KB Output is correct
12 Correct 7 ms 1884 KB Output is correct
13 Correct 13 ms 2648 KB Output is correct
14 Correct 6 ms 1628 KB Output is correct
15 Correct 15 ms 3156 KB Output is correct

Subtask #7
5.0 / 5.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

Subtask #8
15.0 / 15.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 436 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 600 KB Output is correct

Subtask #9
15.0 / 15.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 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 380 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 11 ms 2772 KB Output is correct
10 Correct 9 ms 2516 KB Output is correct
11 Correct 4 ms 1496 KB Output is correct
12 Correct 5 ms 1496 KB Output is correct
13 Correct 2 ms 604 KB Output is correct

Subtask #10
10.0 / 10.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 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 13 ms 3116 KB Output is correct
10 Correct 9 ms 2516 KB Output is correct
11 Correct 5 ms 1496 KB Output is correct
12 Correct 5 ms 1492 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 15 ms 4192 KB Output is correct
15 Correct 17 ms 4656 KB Output is correct
16 Correct 4 ms 1240 KB Output is correct
17 Correct 11 ms 2772 KB Output is correct
18 Correct 7 ms 2260 KB Output is correct