# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1071105 | Plurm | Ancient Machine (JOI21_ancient_machine) | C++17 | 64 ms | 17000 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 {
void dfs1(vector<vector<int>> &g, vector<int> &col, vector<int> &stk, int u) {
if (col[u])
return;
col[u] = -1;
for (int v : g[u]) {
dfs1(g, col, stk, v);
}
stk.push_back(u);
}
void dfs2(vector<vector<int>> &rg, vector<int> &col, int cc, int u) {
if (col[u] >= 0)
return;
col[u] = cc;
for (int v : rg[u]) {
dfs2(rg, col, cc, v);
}
}
vector<int> get_scc(vector<vector<int>> g) {
vector<vector<int>> rg(g.size());
for (int i = 0; i < g.size(); i++) {
for (int j : g[i])
rg[j].push_back(i);
}
vector<int> col(g.size(), 0);
vector<int> stk;
for (int i = 0; i < g.size(); i++)
dfs1(g, col, stk, i);
int ccnt = 0;
while (!stk.empty()) {
int u = stk.back();
stk.pop_back();
if (col[u] == -1)
dfs2(rg, col, ccnt++, u);
}
return col;
}
} // namespace
void Bruno(int N, int L, std::vector<int> A) {
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');
}
vector<vector<int>> g(N);
for (int i = 0; i < N; i++) {
if (target[i] != 'Y')
continue;
int x = -1;
for (int j = i - 1; j >= 0; j--) {
if (target[j] == 'X') {
x = j;
break;
}
}
int z = N;
for (int j = i + 1; j < N; j++) {
if (target[j] == 'Z') {
z = j;
break;
}
}
if (x == -1 || z == N)
continue;
for (int j = x + 1; j < z; j++) {
if (j == i)
continue;
g[j].push_back(i);
}
}
vector<int> sccnum = get_scc(g);
vector<int> ord(N);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(),
[&sccnum](int x, int y) { return sccnum[x] < sccnum[y]; });
for (int x : ord)
Remove(x);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |