oj.uz

Submission #589399

# Submission time Handle Problem Language Result Execution time Memory
589399 2022-07-04T14:52:15 Z Do_you_copy Gondola (IOI14_gondola) C++14
100 / 100
 63 ms 6328 KB 
#include <bits/stdc++.h>
#include <gondola.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using pii = pair <int, int>;
using pil = pair <int, ll>;
using pli = pair <ll, int>;
using pll = pair <ll, ll>;
using ull = unsigned ll;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());
 
ll min(const ll &a, const ll &b){
    return (a < b) ? a : b;
}
 
ll max(const ll &a, const ll &b){
    return (a > b) ? a : b;
}
 
const ll Mod = 1000000009;
const ll Mod2 = 999999999989;
const int maxN = 25e4 + 1;
int mp[maxN];
int n;
 
ll power(int x, int y){
    if (y == 0) return 1;
    if (y == 1) return x;
    ll t = power(x, y / 2);
    if (y % 2) return t * t % Mod * x % Mod;
    else return t * t % Mod;
}
 
int valid(int N, int inputSeq[]){
    n = N;
    int pivot, cnt = 0, tem = INT_MAX;
    for (int i = 0; i < n; ++i){
        if (mp[inputSeq[i]]) return 0;
        mp[inputSeq[i]] = 1;
        if (inputSeq[i] > n) ++cnt;
        if (tem > inputSeq[i]){
            tem = inputSeq[i];
            pivot = i;
        }
    }
    if (cnt == n) return 1;
    //pivot is where the number one is supposed to be at
    pivot = ((pivot - tem + 1) + n) % n;
    for (int i = pivot; i < pivot + n; ++i){
        if (inputSeq[i % n] <= n && inputSeq[i % n] != i - pivot + 1){
            return 0;
        }
    }
    return 1;
}
 
int replacement(int N, int gondolaSeq[], int replacementSeq[]){
    n = N;
    int pivot = n - 1, tem = n, maxx = 0;
    for (int i = 0; i < n; ++i){
        if (tem > gondolaSeq[i]){
            tem = gondolaSeq[i];
            pivot = i;
        }
        maxx = max(maxx, gondolaSeq[i]);
        mp[gondolaSeq[i]] = i + 1;
    }
    pivot = ((pivot - tem + 1) + n) % n;
    vector <int> a(n);
    vector <int> b;
    for (int i = n + 1; i <= maxx; ++i){
        if (!mp[i]) b.pb(i);
    }
    for (int i = pivot; i < pivot + n; ++i){
        a[i % n] = i - pivot + 1;
    }
    vector <int> ans;
    while (!b.empty()){
        int k = b.back();
        b.pop_back();
        ans.pb(k);
        gondolaSeq[mp[maxx] - 1] = k;
        mp[k] = mp[maxx];
        --maxx;
    }
    while (maxx > n){
        int k = a[mp[maxx] - 1];
        ans.pb(k);
        //gondolaSeq[mp[maxx] - 1] = k;
        --maxx;
    }
    for (int i = 0; i < ans.size(); ++i) replacementSeq[i] = ans[ans.size() - i - 1];
    return ans.size();
}
 
int countReplacement(int N, int inputSeq[]){
    n = N;
    int pivot, cnt = 0, tem = INT_MAX;
    map <int, int> mp;
    vector <int> a;
    ll ans = 1;
    for (int i = 0; i < n; ++i){
        if (mp[inputSeq[i]]) return 0;
        mp[inputSeq[i]] = 1;
        if (inputSeq[i] > n){
            ++cnt;
            a.pb(inputSeq[i]);
        }
        if (tem > inputSeq[i]){
            tem = inputSeq[i];
            pivot = i;
        }
    }
    if (cnt == n){
        ans = n;
    }
    //pivot is where the number one is supposed to be at
    pivot = ((pivot - tem + 1) % n + n) % n;
    for (int i = pivot; i < pivot + n; ++i){
        if (inputSeq[i % n] <= n && inputSeq[i % n] != i - pivot + 1){
            return 0;
        }
    }
    sort(a.begin(), a.end());
    int last = n;
    for (int i = 0; i < a.size(); ++i){
        ans = ans * power(a.size() - i, a[i] - last - 1) % Mod;
        last = a[i];
    }
    return ans;
}

Compilation message

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:97:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for (int i = 0; i < ans.size(); ++i) replacementSeq[i] = ans[ans.size() - i - 1];
      |                     ~~^~~~~~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:131:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |     for (int i = 0; i < a.size(); ++i){
      |                     ~~^~~~~~~~~~
gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:53:21: warning: 'pivot' may be used uninitialized in this function [-Wmaybe-uninitialized]
   53 |     pivot = ((pivot - tem + 1) + n) % n;
      |               ~~~~~~^~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:123:21: warning: 'pivot' may be used uninitialized in this function [-Wmaybe-uninitialized]
  123 |     pivot = ((pivot - tem + 1) % n + n) % n;
      |               ~~~~~~^~~~~

Subtask #1
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 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 316 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 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 5 ms 724 KB Output is correct
7 Correct 13 ms 1024 KB Output is correct
8 Correct 7 ms 980 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 8 ms 980 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 320 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 5 ms 664 KB Output is correct
7 Correct 9 ms 1088 KB Output is correct
8 Correct 9 ms 924 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 12 ms 980 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 5 ms 1348 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 8 ms 1164 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 0 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 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 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 1 ms 212 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 452 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct

Subtask #6
20.0 / 20.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 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 1 ms 312 KB Output is correct
8 Correct 1 ms 444 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 8 ms 1312 KB Output is correct
12 Correct 10 ms 1400 KB Output is correct
13 Correct 12 ms 1940 KB Output is correct
14 Correct 9 ms 1344 KB Output is correct
15 Correct 26 ms 3272 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 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 1 ms 320 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 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 312 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 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 1 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 4308 KB Output is correct
10 Correct 31 ms 3716 KB Output is correct
11 Correct 12 ms 1604 KB Output is correct
12 Correct 15 ms 1932 KB Output is correct
13 Correct 3 ms 724 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 1 ms 212 KB Output is correct
4 Correct 1 ms 280 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 316 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 320 KB Output is correct
9 Correct 43 ms 4396 KB Output is correct
10 Correct 30 ms 3636 KB Output is correct
11 Correct 12 ms 1648 KB Output is correct
12 Correct 14 ms 1960 KB Output is correct
13 Correct 4 ms 724 KB Output is correct
14 Correct 49 ms 5684 KB Output is correct
15 Correct 63 ms 6328 KB Output is correct
16 Correct 9 ms 1364 KB Output is correct
17 Correct 39 ms 4364 KB Output is correct
18 Correct 21 ms 2552 KB Output is correct