oj.uz

답안 #1071248

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1071248 2024-08-23T06:12:35 Z Plurm Ancient Machine (JOI21_ancient_machine) C++17
5 / 100
 2000 ms 10980 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 (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;
        }
        if (target[ok.second] == '\0')
            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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1036 KB Output is correct
2 Correct 0 ms 1048 KB Output is correct
3 Correct 1 ms 1032 KB Output is correct
4 Correct 0 ms 1048 KB Output is correct
5 Correct 0 ms 1048 KB Output is correct
6 Correct 2 ms 1048 KB Output is correct
7 Correct 1 ms 1048 KB Output is correct
8 Correct 0 ms 1040 KB Output is correct
9 Correct 1 ms 1036 KB Output is correct
10 Correct 1 ms 1036 KB Output is correct
11 Correct 0 ms 1048 KB Output is correct

Subtask #2
0 / 95.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 56 ms 10736 KB Partially correct
2 Partially correct 60 ms 10836 KB Partially correct
3 Partially correct 68 ms 10668 KB Partially correct
4 Partially correct 56 ms 10696 KB Partially correct
5 Partially correct 83 ms 10772 KB Partially correct
6 Partially correct 69 ms 10732 KB Partially correct
7 Partially correct 66 ms 10708 KB Partially correct
8 Partially correct 56 ms 10696 KB Partially correct
9 Partially correct 55 ms 10688 KB Partially correct
10 Partially correct 69 ms 10804 KB Partially correct
11 Partially correct 59 ms 10744 KB Partially correct
12 Partially correct 69 ms 10980 KB Partially correct
13 Execution timed out 2096 ms 6228 KB Time limit exceeded
14 Halted 0 ms 0 KB -