oj.uz

Submission #285524

# Submission time Handle Problem Language Result Execution time Memory
285524 2020-08-29T08:00:26 Z 2qbingxuan Gondola (IOI14_gondola) C++14
25 / 100
 29 ms 1664 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);
        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;
}

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

int countReplacement(int n, int inputSeq[])
{
  return -3;
}

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 1 ms 256 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 256 KB Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 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 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 9 ms 896 KB Output is correct
7 Correct 18 ms 1408 KB Output is correct
8 Correct 14 ms 1408 KB Output is correct
9 Correct 6 ms 640 KB Output is correct
10 Correct 19 ms 1664 KB Output is correct
11 Correct 0 ms 256 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 9 ms 768 KB Output is correct
14 Correct 0 ms 256 KB Output is correct
15 Correct 29 ms 1664 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Incorrect 1 ms 384 KB Integer 4331 violates the range [1, 72]
9 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 380 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Incorrect 1 ms 360 KB Integer 4331 violates the range [1, 72]
9 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -