Submission #1071248

#TimeUsernameProblemLanguageResultExecution timeMemory
1071248PlurmAncient Machine (JOI21_ancient_machine)C++17
5 / 100
2096 ms10980 KiB
#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 (stderr)

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;
      |         ^~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...