#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) {
set<int> active;
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;
set<pair<int, int>> pq;
vector<int> prefX(N, -1);
for (int i = 0; i < N; i++) {
active.insert(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.insert({-c, i});
}
}
vector<int> ord;
int chosen = -1;
while (!pq.empty()) {
auto ok = *pq.begin();
pq.erase(ok);
if (target[ok.second] == '\0')
continue;
if (sum(suffZ[ok.second] - 1) - sum(prefX[ok.second]) - 1 !=
-ok.first) {
pq.insert({-(sum(suffZ[ok.second] - 1) - sum(prefX[ok.second]) - 1),
ok.second});
continue;
}
auto it = active.lower_bound(prefX[ok.second] + 1);
while (it != active.end() && *it < suffZ[ok.second]) {
int j = *it;
if (j == ok.second) {
++it;
continue;
}
if (target[j] != '\0') {
target[j] = '\0';
add(j, -1);
ord.push_back(j);
it = active.erase(it);
} else {
++it;
}
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:37:10: warning: unused variable 'done' [-Wunused-variable]
37 | bool done = false;
| ^~~~
Bruno.cpp:62:9: warning: unused variable 'chosen' [-Wunused-variable]
62 | int chosen = -1;
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1048 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1048 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1040 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1040 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
1032 KB |
Wrong Answer [6] |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
95 ms |
12796 KB |
Wrong Answer [6] |
| 2 |
Halted |
0 ms |
0 KB |
- |
