oj.uz

Submission #734984

# Submission time Handle Problem Language Result Execution time Memory
734984 2023-05-03T10:39:49 Z sandry24 Gondola (IOI14_gondola) C++17
100 / 100
 54 ms 7112 KB 
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define pb push_back
#define mp make_pair
#define f first
#define s second

#include "gondola.h"

map<int, int> freq;

int valid(int n, int inputSeq[]){
    int index_under_n = -1;
    for(int i = 0; i < n; i++){
        freq[inputSeq[i]]++;
        if(freq[inputSeq[i]] > 1)
            return 0;
        if(inputSeq[i] <= n)
            index_under_n = i;
    }
    if(index_under_n == -1)
        return 1;
    int index = (index_under_n == n-1 ? 0 : index_under_n + 1);
    int next = (inputSeq[index_under_n] == n ? 1 : inputSeq[index_under_n] + 1);
    while(index != index_under_n){
        if(inputSeq[index] < n){
            if(inputSeq[index] != next){
                return 0;
            }
        }
        index = (index == n-1 ? 0 : index + 1);
        next = (next == n ? 1 : next + 1);
    }
    return 1;
}

int replacement(int n, int gondolaSeq[], int replacementSeq[]){
    int index = -1, cnt = 0, next;
    for(int i = 0; i < n; i++)
        if(gondolaSeq[i] <= n)
            index = i;
    if(index == -1){
        index = 0;
        next = 1;
    } else next = gondolaSeq[index];
    vector<pi> temp;
    int current = n+1;
    while(cnt != n){
        if(gondolaSeq[index] != next)
            temp.pb({gondolaSeq[index], next});
        index = (index == n-1 ? 0 : index + 1);
        next = (next == n ? 1 : next + 1);
        cnt++;
    }
    sort(temp.begin(), temp.end());
    int ind = 0;
    for(int i = 0; i < temp.size(); i++){
        while(temp[i].f != temp[i].s){
            replacementSeq[ind] = temp[i].s;
            temp[i].s = current;
            current++;
            ind++;
        }
    }
    return ind;
}

ll bin_pow(ll a, ll b, ll mod){
    ll ans = 1;
    while(b > 0){
        if(b & 1)
            ans = ans * a % mod;
        a = a * a % mod;
        b /= 2;
    }
    return ans;
}

int countReplacement(int n, int inputSeq[]){
    if(!valid(n, inputSeq))
        return 0;
    vector<ll> temp;
    for(int i = 0; i < n; i++)
        if(inputSeq[i] > n)
            temp.pb(inputSeq[i]);
    ll ans = 1, mod = 1e9+9, current = n+1;
    sort(temp.begin(), temp.end());
    for(int i = 0; i < temp.size(); i++){
        ll diff = temp[i] - current;
        ans *= bin_pow(temp.size() - i, diff, mod);
        ans %= mod;
        current = temp[i] + 1;
    }
    if(temp.size() == n){
        ans *= n;
        ans %= mod;
    }
    return ans;
}

Compilation message

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:63:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for(int i = 0; i < temp.size(); i++){
      |                    ~~^~~~~~~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:94:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for(int i = 0; i < temp.size(); i++){
      |                    ~~^~~~~~~~~~~~~
gondola.cpp:100:20: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  100 |     if(temp.size() == n){
      |        ~~~~~~~~~~~~^~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 13 ms 2132 KB Output is correct
7 Correct 8 ms 596 KB Output is correct
8 Correct 24 ms 3856 KB Output is correct
9 Correct 8 ms 1364 KB Output is correct
10 Correct 30 ms 4512 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 12 ms 2192 KB Output is correct
7 Correct 8 ms 596 KB Output is correct
8 Correct 22 ms 3920 KB Output is correct
9 Correct 7 ms 1364 KB Output is correct
10 Correct 30 ms 4488 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 14 ms 1980 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 37 ms 4588 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 7 ms 596 KB Output is correct
12 Correct 7 ms 596 KB Output is correct
13 Correct 15 ms 1168 KB Output is correct
14 Correct 6 ms 596 KB Output is correct
15 Correct 18 ms 2252 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 39 ms 4624 KB Output is correct
10 Correct 30 ms 4044 KB Output is correct
11 Correct 11 ms 1764 KB Output is correct
12 Correct 14 ms 1988 KB Output is correct
13 Correct 3 ms 732 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 224 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 39 ms 4680 KB Output is correct
10 Correct 29 ms 4044 KB Output is correct
11 Correct 11 ms 1784 KB Output is correct
12 Correct 14 ms 2088 KB Output is correct
13 Correct 3 ms 704 KB Output is correct
14 Correct 53 ms 6452 KB Output is correct
15 Correct 54 ms 7112 KB Output is correct
16 Correct 9 ms 1748 KB Output is correct
17 Correct 38 ms 4704 KB Output is correct
18 Correct 19 ms 3104 KB Output is correct