oj.uz

Submission #585749

# Submission time Handle Problem Language Result Execution time Memory
585749 2022-06-29T09:51:13 Z stevancv Gondola (IOI14_gondola) C++14
100 / 100
 54 ms 6296 KB 
#include <bits/stdc++.h>
#include "gondola.h"
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
vector<int> Make(int n, int a[]) {
    vector<int> b(n);
    int ind = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] <= n) ind = (i + n + 1 - a[i]) % n;
    }
    for (int i = ind; i < ind + n; i++) {
        b[i % n] = i - ind + 1;
    }
    return b;
}
int valid(int n, int a[]) {
    map<int, int> mp;
    for (int i = 0; i < n; i++) {
        if (mp[a[i]] == 1) return 0;
        mp[a[i]]++;
    }
    vector<int> v = Make(n, a);
    for (int i = 0; i < n; i++) {
        if (a[i] <= n && a[i] != v[i]) return 0;
    }
    return 1;
}
int replacement(int n, int a[], int b[]) {
    vector<int> v = Make(n, a);
    vector<pair<int, int>> all;
    for (int i = 0; i < n; i++) {
        if (a[i] > n) all.push_back({a[i], v[i]});
    }
    sort(all.begin(), all.end());
    vector<int> ans;
    int prv = n + 1;
    for (int i = 0; i < all.size(); i++) {
        ans.push_back(all[i].second);
        for (int j = prv; j < all[i].first; j++) ans.push_back(j);
        prv = all[i].first + 1;
    }
    for (int i = 0; i < ans.size(); i++) b[i] = ans[i];
    return ans.size();
}
int mod = 1e9 + 9;
int Mul(int a, int b) {
    ll c = a; c *= b; c %= mod;
    return c;
}
int Exp(int a, int b) {
    int ans = 1;
    while (b > 0) {
        if (b & 1) ans = Mul(ans, a);
        a = Mul(a, a);
        b >>= 1;
    }
    return ans;
}
int countReplacement(int n, int a[]) {
    if (!valid(n, a)) return 0;
    vector<int> v;
    v.push_back(n);
    for (int i = 0; i < n; i++) {
        if (a[i] > n) v.push_back(a[i]);
    }
    sort(v.begin(), v.end());
    int ans = 1;
    int x = v.size();
    if (x == n + 1) ans = n;
    for (int i = 1; i < x; i++) {
        ans = Mul(ans, Exp(x - i, v[i] - v[i - 1] - 1));
    }
    return ans;
}

Compilation message

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for (int i = 0; i < all.size(); i++) {
      |                     ~~^~~~~~~~~~~~
gondola.cpp:47:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for (int i = 0; i < ans.size(); i++) b[i] = ans[i];
      |                     ~~^~~~~~~~~~~~

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 1 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 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 12 ms 2260 KB Output is correct
7 Correct 13 ms 596 KB Output is correct
8 Correct 23 ms 4128 KB Output is correct
9 Correct 7 ms 1556 KB Output is correct
10 Correct 31 ms 4852 KB Output is correct

Subtask #3
10.0 / 10.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 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 13 ms 2356 KB Output is correct
7 Correct 12 ms 624 KB Output is correct
8 Correct 23 ms 4140 KB Output is correct
9 Correct 7 ms 1504 KB Output is correct
10 Correct 28 ms 4836 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 15 ms 2212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 38 ms 4944 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 1 ms 212 KB Output is correct

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

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 1 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 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 852 KB Output is correct
12 Correct 8 ms 980 KB Output is correct
13 Correct 14 ms 1492 KB Output is correct
14 Correct 11 ms 852 KB Output is correct
15 Correct 24 ms 2200 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 0 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 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 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 1 ms 212 KB Output is correct
9 Correct 40 ms 4764 KB Output is correct
10 Correct 34 ms 3956 KB Output is correct
11 Correct 11 ms 1584 KB Output is correct
12 Correct 14 ms 1876 KB Output is correct
13 Correct 3 ms 596 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 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 1 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 212 KB Output is correct
9 Correct 41 ms 4800 KB Output is correct
10 Correct 34 ms 3924 KB Output is correct
11 Correct 14 ms 1644 KB Output is correct
12 Correct 16 ms 1960 KB Output is correct
13 Correct 4 ms 596 KB Output is correct
14 Correct 48 ms 5576 KB Output is correct
15 Correct 54 ms 6296 KB Output is correct
16 Correct 9 ms 1364 KB Output is correct
17 Correct 35 ms 4396 KB Output is correct
18 Correct 20 ms 2564 KB Output is correct