oj.uz

Submission #285544

# Submission time Handle Problem Language Result Execution time Memory
285544 2020-08-29T08:34:55 Z 2qbingxuan Gondola (IOI14_gondola) C++14
100 / 100
 37 ms 2960 KB 
#include "gondola.h"
#include <bits/stdc++.h>
#ifdef local
#define debug(...) qqbx(#__VA_ARGS__, __VA_ARGS__)
void qqbx(const char *s) {}
template <typename H, typename ...T> void qqbx(const char *s, const H& h, T&& ...args) {
    for(; *s && *s != ','; ++s) if(*s != ' ') std::cerr << *s;
    std::cerr << " = " << h << (sizeof...(T) ? ", " : "\n");
    if(sizeof...(T)) qqbx(++s, args...);
}
#define safe std::cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#else
#define debug(...) ((void)0)
#define safe ((void)0)
#endif // local
#define pb emplace_back
#define all(v) begin(v),end(v)
using namespace std;

int valid(int n, int inputSeq[]) {
    vector<int> v(inputSeq, inputSeq+n), u = v;
    sort(u.begin(), u.end());
    for(int i = 1; i < n; i++) if(u[i] == u[i-1]) return false;
    for(int &x: v) --x;
    queue<int> q;
    for(int i = 0; i < n; i++) if(v[i] < n) q.push(i);
    while(!q.empty()) {
        int i = q.front(); q.pop();
        int j = (i+1)%n;
        if(v[j] >= n) {
            v[j] = (v[i]+1)%n;
            q.push(j);
        } else if(v[j] != (v[i]+1)%n) {
            return false;
        }
    }
    return true;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
    int L = 0;
    int tot = n;
    vector<int> v(gondolaSeq, gondolaSeq+n), org = v;
    {
        for(int &x: org) --x;
        queue<int> q;
        for(int i = 0; i < n; i++) if(org[i] < n) q.push(i);
        if(q.empty()) {
            for(int i = 0; i < n; i++) org[i] = i+1;
        } else {
            while(!q.empty()) {
                int i = q.front(); q.pop();
                int j = (i+1)%n;
                if(org[j] >= n) {
                    org[j] = (org[i]+1)%n;
                    q.push(j);
                } else {
                    assert(org[j] == (org[i]+1)%n);
                }
            }
            for(int &x: org) ++x;
        }
    }
    vector<pair<int,int>> evt;
    for(int i = 0; i < n; i++) if(v[i] > n) evt.pb(v[i], i);
    sort(evt.begin(), evt.end());
    for(int i = 0; i < int(evt.size()); i++)
        while(tot < evt[i].first) replacementSeq[L++] = org[evt[i].second], org[evt[i].second] = ++tot;
    return L;
}

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

const int MOD = 1000000009;
int modpow(long long e, int p) {
    long long r = 1;
    for(; p; p>>=1, e=e*e%MOD) if(p&1) r = r*e%MOD;
    return r;
}
int countReplacement(int n, int inputSeq[]) {
    if(!valid(n, inputSeq)) return 0;
    vector<int> v(inputSeq, inputSeq+n);
    vector<pair<int,int>> evt;
    for(int i = 0; i < n; i++) if(v[i] > n) evt.pb(v[i], i);
    sort(evt.begin(), evt.end());
    int tot = n;
    long long ans = 1;
    for(int i = 0; i < int(evt.size()); i++) {
        // tot+1, tot+2, ... evt[i].first-1 can be arbitary placed on evt.size()-i positions
        debug(evt.size()-i, evt[i].first - tot - 1);
        ans = ans * modpow(int(evt.size()) - i, evt[i].first - tot - 1) % MOD;
        tot = evt[i].first;
    }
    if(evt.size() == n) ans = ans * n % MOD;
    return ans;
}

Compilation message

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:96:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   96 |     if(evt.size() == n) ans = ans * n % MOD;
      |        ~~~~~~~~~~~^~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 10 ms 928 KB Output is correct
7 Correct 20 ms 1408 KB Output is correct
8 Correct 15 ms 1404 KB Output is correct
9 Correct 6 ms 640 KB Output is correct
10 Correct 21 ms 1664 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 288 KB Output is correct
6 Correct 11 ms 896 KB Output is correct
7 Correct 19 ms 1408 KB Output is correct
8 Correct 15 ms 1408 KB Output is correct
9 Correct 7 ms 640 KB Output is correct
10 Correct 20 ms 1656 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 0 ms 256 KB Output is correct
13 Correct 9 ms 768 KB Output is correct
14 Correct 0 ms 256 KB Output is correct
15 Correct 22 ms 1664 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 14 ms 1536 KB Output is correct
12 Correct 15 ms 1784 KB Output is correct
13 Correct 19 ms 1532 KB Output is correct
14 Correct 13 ms 1536 KB Output is correct
15 Correct 26 ms 2424 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 26 ms 1720 KB Output is correct
10 Correct 21 ms 1568 KB Output is correct
11 Correct 11 ms 848 KB Output is correct
12 Correct 11 ms 936 KB Output is correct
13 Correct 3 ms 512 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 26 ms 1728 KB Output is correct
10 Correct 21 ms 1568 KB Output is correct
11 Correct 9 ms 848 KB Output is correct
12 Correct 10 ms 936 KB Output is correct
13 Correct 3 ms 512 KB Output is correct
14 Correct 36 ms 2792 KB Output is correct
15 Correct 37 ms 2960 KB Output is correct
16 Correct 7 ms 1016 KB Output is correct
17 Correct 24 ms 1920 KB Output is correct
18 Correct 14 ms 1640 KB Output is correct