oj.uz

답안 #960176

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
960176 2024-04-09T19:55:26 Z Nelt 곤돌라 (IOI14_gondola) C++17
90 / 100
 144 ms 262144 KB 
#include "gondola.h"
#include <bits/stdc++.h>

#define ll long long
#define endl "\n"

using namespace std;
const ll mod = 1e9 + 9;
ll binpow(ll n, ll p)
{
    ll ans = 1;
    n %= mod;
    while (p)
    {
        ans = (p & 1 ? ans * n % mod : ans);
        p >>= 1;
        n = n * n % mod;
    }
    return ans;
}
int valid(int n, int a[])
{
    set<ll> s;
    for (ll i = 0; i < n; i++)
        s.insert(a[i]);
    if (s.size() != n)
        return 0;
    ll st = -1, b[n];
    for (ll i = 0; i < n; i++)
        if (a[i] <= n)
            st = i;
    if (st == -1)
        return 1;
    b[st] = a[st];
    for (ll i = st + 1; i < st + n; i++)
        b[i % n] = b[(i - 1 + n) % n] % n + 1;
    // for (ll i = 0; i < n; i++)
    //     cout << b[i] << " ";
    // cout << endl;
    for (ll i = 0; i < n; i++)
        if (a[i] <= n and a[i] != b[i])
            return 0;
    return 1;
}

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

int replacement(int n, int a[], int replacementSeq[])
{
    ll st = -1, b[n];
    for (ll i = 0; i < n; i++)
        if (a[i] <= n)
            st = i;
    if (st == -1)
        iota(b, b + n, 1);
    else
    {
        b[st] = a[st];
        for (ll i = st + 1; i < st + n; i++)
            b[i % n] = b[(i - 1 + n) % n] % n + 1;
    }
    ll ptr = 0, mx = max_element(a, a + n) - a;
    ll ind[a[mx] + 1];
    for (ll i = 0; i <= a[mx]; i++)
        ind[i] = -1;
    for (ll i = 0; i < n; i++)
        ind[a[i]] = i;
    for (ll i = n + 1; i <= a[mx]; i++)
        if (ind[i] != -1)
            replacementSeq[ptr++] = b[ind[i]], b[ind[i]] = i;
        else
            replacementSeq[ptr++] = b[mx], b[mx] = i;
    return ptr;
}

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

int countReplacement(int n, int a[])
{
    if (!valid(n, a))
        return 0;
    ll ans = 1, mx = max_element(a, a + n) - a;
    ll ind[a[mx] + 1];
    for (ll i = 0; i <= a[mx]; i++)
        ind[i] = -1;
    for (ll i = 0; i < n; i++)
        ind[a[i]] = i;
    ll b[n];
    for (ll i = 0; i < n; i++)
        b[i] = a[i];
    sort(b, b + n, greater());
    for (ll i = 0; i < n and b[i] > n; i++)
        ans = ans * binpow(i + 1, b[i] - max((ll)n, i + 1 < n ? b[i + 1] : 1) - 1) % mod;
    if (b[n - 1] > n)
        ans = ans * n % mod;
    return ans;
}

Compilation message

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:26:18: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   26 |     if (s.size() != n)
      |         ~~~~~~~~~^~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:83:8: warning: variable 'ind' set but not used [-Wunused-but-set-variable]
   83 |     ll ind[a[mx] + 1];
      |        ^~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 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 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 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 10 ms 2648 KB Output is correct
7 Correct 19 ms 4188 KB Output is correct
8 Correct 15 ms 4956 KB Output is correct
9 Correct 5 ms 1884 KB Output is correct
10 Correct 19 ms 5724 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 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 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 8 ms 2648 KB Output is correct
7 Correct 24 ms 4164 KB Output is correct
8 Correct 19 ms 4948 KB Output is correct
9 Correct 5 ms 1884 KB Output is correct
10 Correct 22 ms 5660 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 10 ms 2652 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 25 ms 6232 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 548 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

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 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
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 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
6 Correct 0 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 7 ms 2396 KB Output is correct
12 Correct 13 ms 2652 KB Output is correct
13 Correct 10 ms 2396 KB Output is correct
14 Correct 7 ms 2392 KB Output is correct
15 Correct 19 ms 3932 KB Output is correct

Subtask #7
5.0 / 5.0

# 결과 실행 시간 메모리 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

Subtask #8
15.0 / 15.0

# 결과 실행 시간 메모리 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 1 ms 344 KB Output is correct
6 Correct 1 ms 352 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #9
15.0 / 15.0

# 결과 실행 시간 메모리 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 0 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 28 ms 6528 KB Output is correct
10 Correct 22 ms 5468 KB Output is correct
11 Correct 9 ms 3420 KB Output is correct
12 Correct 10 ms 3020 KB Output is correct
13 Correct 3 ms 2396 KB Output is correct

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 27 ms 6644 KB Output is correct
10 Correct 22 ms 5208 KB Output is correct
11 Correct 8 ms 3420 KB Output is correct
12 Correct 10 ms 3164 KB Output is correct
13 Correct 3 ms 2392 KB Output is correct
14 Runtime error 144 ms 262144 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -