oj.uz

Submission #1071249

# Submission time Handle Problem Language Result Execution time Memory
1071249 2024-08-23T06:14:08 Z Plurm Ancient Machine (JOI21_ancient_machine) C++17
5 / 100
 2000 ms 11184 KB 
#include "Anna.h"
#include <vector>

namespace {

int variable_example = 0;

}

void Anna(int N, std::vector<char> S) {
    for (int i = 0; i < N; i++) {
        if (S[i] == 'X') {
            Send(0);
        } else if (S[i] == 'Y') {
            Send(1);
            Send(0);
        } else {
            Send(1);
            Send(1);
        }
    }
}

#include "Bruno.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
int FT[100005];
void add(int idx, int amt) {
    idx++;
    while (idx < 100005) {
        FT[idx] += amt;
        idx += idx & -idx;
    }
}
int sum(int idx) {
    idx++;
    int ret = 0;
    while (idx > 0) {
        ret += FT[idx];
        idx -= idx & -idx;
    }
    return ret;
}
} // namespace

void Bruno(int N, int L, std::vector<int> A) {
    memset(FT, 0, sizeof(FT));
    string target;
    int ptr = 0;
    while (ptr < L) {
        if (A[ptr++] == 0)
            target.push_back('X');
        else if (A[ptr++] == 0)
            target.push_back('Y');
        else
            target.push_back('Z');
    }
    bool done = false;
    priority_queue<pair<int, int>> pq;
    vector<int> prefX(N, -1);
    for (int i = 0; i < N; i++) {
        add(i, 1);
        if (target[i] == 'X')
            prefX[i] = i;
        else
            prefX[i] = i ? prefX[i - 1] : -1;
    }
    vector<int> suffZ(N, N);
    for (int i = N - 1; i >= 0; i--) {
        if (target[i] == 'Z')
            suffZ[i] = i;
        else
            suffZ[i] = i == N - 1 ? N : suffZ[i + 1];
    }
    for (int i = 0; i < N; i++) {
        if (target[i] == 'Y' && prefX[i] != -1 && suffZ[i] != N) {
            int c = suffZ[i] - prefX[i] - 2;
            pq.push({-c, i});
        }
    }
    vector<int> ord;
    int chosen = -1;
    while (!pq.empty()) {
        auto ok = pq.top();
        pq.pop();
      if (target[ok.second] == '\0')
            continue;
        if (sum(suffZ[ok.second] - 1) - sum(prefX[ok.second]) - 1 !=
            -ok.first) {
            pq.push({-(sum(suffZ[ok.second] - 1) - sum(prefX[ok.second]) - 1),
                     ok.second});
            continue;
        }
        for (int j = prefX[ok.second] + 1; j < suffZ[ok.second]; j++) {
            if (j == ok.second)
                continue;
            if (target[j] != '\0') {
                target[j] = '\0';
                add(j, -1);
                ord.push_back(j);
            }
            prefX[j] = prefX[ok.second];
            suffZ[j] = suffZ[ok.second];
        }
        target[ok.second] = '\0';
        add(ok.second, -1);
        ord.push_back(ok.second);
    }
    for (int i = 0; i < N; i++) {
        if (target[i] != '\0')
            ord.push_back(i);
    }
    for (int x : ord)
        Remove(x);
}

Compilation message

Anna.cpp:6:5: warning: '{anonymous}::variable_example' defined but not used [-Wunused-variable]
    6 | int variable_example = 0;
      |     ^~~~~~~~~~~~~~~~

Bruno.cpp: In function 'void Bruno(int, int, std::vector<int>)':
Bruno.cpp:36:10: warning: unused variable 'done' [-Wunused-variable]
   36 |     bool done = false;
      |          ^~~~
Bruno.cpp:60:9: warning: unused variable 'chosen' [-Wunused-variable]
   60 |     int chosen = -1;
      |         ^~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1040 KB Output is correct
2 Correct 0 ms 1036 KB Output is correct
3 Correct 0 ms 1040 KB Output is correct
4 Correct 0 ms 1040 KB Output is correct
5 Correct 1 ms 1052 KB Output is correct
6 Correct 0 ms 1040 KB Output is correct
7 Correct 0 ms 1048 KB Output is correct
8 Correct 0 ms 1040 KB Output is correct
9 Correct 0 ms 1052 KB Output is correct
10 Correct 0 ms 1052 KB Output is correct
11 Correct 0 ms 1040 KB Output is correct

Subtask #2
0 / 95.0

# Verdict Execution time Memory Grader output
1 Partially correct 55 ms 10872 KB Partially correct
2 Partially correct 56 ms 10868 KB Partially correct
3 Partially correct 56 ms 10872 KB Partially correct
4 Partially correct 60 ms 11184 KB Partially correct
5 Partially correct 59 ms 10860 KB Partially correct
6 Partially correct 56 ms 10888 KB Partially correct
7 Partially correct 57 ms 10896 KB Partially correct
8 Partially correct 57 ms 10848 KB Partially correct
9 Partially correct 59 ms 10840 KB Partially correct
10 Partially correct 58 ms 10844 KB Partially correct
11 Partially correct 56 ms 10872 KB Partially correct
12 Partially correct 52 ms 10848 KB Partially correct
13 Execution timed out 2015 ms 6040 KB Time limit exceeded
14 Halted 0 ms 0 KB -