oj.uz

Submission #1071226

# Submission time Handle Problem Language Result Execution time Memory
1071226 2024-08-23T06:03:46 Z sleepntsheep Ancient Machine (JOI21_ancient_machine) C++17
40 / 100
 126 ms 19404 KB 
#include "Anna.h"
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

namespace {
}

void Anna(int N, std::vector<char> S) {
	vector<int> v;
	for (int i = 0; i < N; ++i) 
		v.push_back(S[i] - 'X');
	while (v.size() < 100000) v.push_back(0);
	for (int i = 0; i < 100000; i += 5) {
		int x = v[i] + v[i + 1] * 3 + v[i + 2] * 3 * 3 + v[i + 3] * 3 * 3 * 3 + v[i + 4] * 3 * 3 * 3 * 3;
		for (int j = 0; j < 8; ++j) Send((x >> j) & 1);
	}
}

#include "Bruno.h"
#include <set>
#include <vector>
#include <algorithm>
using namespace std;

namespace {
	vector<int> decode(int N, vector<int> A) {
		vector<int> v;
		for (int i = 0; i < (int)A.size(); i += 8) {
			int z = 0;
			for (int j = 0; j < 8; ++j) z |= (1 << j) * A[i + j];
			for (int j = 0; j < 5; ++j) v.push_back(z % 3), z /= 3;
		}
		v.resize(N);
		return v;
	}
}

void Bruno(int N, int L, vector<int> A) {
	auto v = decode(N, A);

	set<int> alv;
	vector<int> ded(N);
	for (int i = 0; i < N; ++i) alv.insert(i);

	vector<set<int> > oc(3);
	for (int i = 0; i < N; ++i)
		oc[v[i]].insert(i);

	if (oc[0].empty() or oc[2].empty() or *oc[0].begin() > *oc[2].rbegin()) {
		for (int i = 0; i < N; ++i) Remove(i);
		return;
	}

	int x0 = *oc[0].begin();
	int z0 = *oc[2].rbegin();

	auto REmove = [&](int i) { if (alv.count(i) == 0) return; alv.erase(i); oc[v[i]].erase(i); Remove(i); };
	auto REmove_range = [&](int i, int j) {
		for (auto it = alv.lower_bound(i); it != alv.end() && *it <= j; )
			Remove(*it), oc[v[*it]].erase(*it), it = alv.erase(it);
	};

	int at = x0;
	for (; at < z0 ;) {
		auto zi = oc[2].upper_bound(at);

		while (1) {
			auto yi = oc[1].lower_bound(*zi);
			if (yi == oc[1].begin() or *--yi < x0)
				break;
			auto xi = prev(oc[0].lower_bound(*yi));

			REmove_range(*xi + 1, *yi - 1);
			REmove_range(*yi + 1, *zi - 1);
			REmove(*yi);
			if (*xi != x0) REmove(*xi);
		}
		REmove_range(at + 1, *zi - 1);

		at = *zi;
	}

	for (int i = 0; i < N; ++i) REmove(i);

}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 5092 KB Output is correct
2 Correct 17 ms 5084 KB Output is correct
3 Correct 18 ms 5092 KB Output is correct
4 Correct 18 ms 5080 KB Output is correct
5 Correct 16 ms 5096 KB Output is correct
6 Correct 17 ms 5084 KB Output is correct
7 Correct 17 ms 5088 KB Output is correct
8 Correct 18 ms 5080 KB Output is correct
9 Correct 18 ms 5072 KB Output is correct
10 Correct 18 ms 5068 KB Output is correct
11 Correct 17 ms 5084 KB Output is correct

Subtask #2
35.0 / 95.0

# Verdict Execution time Memory Grader output
1 Partially correct 91 ms 15204 KB Partially correct
2 Partially correct 83 ms 15156 KB Partially correct
3 Partially correct 90 ms 15292 KB Partially correct
4 Partially correct 83 ms 15104 KB Partially correct
5 Partially correct 101 ms 15024 KB Partially correct
6 Partially correct 88 ms 15180 KB Partially correct
7 Partially correct 126 ms 15164 KB Partially correct
8 Partially correct 90 ms 15008 KB Partially correct
9 Partially correct 82 ms 15128 KB Partially correct
10 Partially correct 83 ms 15428 KB Partially correct
11 Partially correct 87 ms 15096 KB Partially correct
12 Partially correct 87 ms 15128 KB Partially correct
13 Partially correct 113 ms 14064 KB Partially correct
14 Partially correct 97 ms 15032 KB Partially correct
15 Partially correct 96 ms 15108 KB Partially correct
16 Partially correct 82 ms 15088 KB Partially correct
17 Partially correct 103 ms 19308 KB Partially correct
18 Partially correct 92 ms 19184 KB Partially correct
19 Partially correct 84 ms 19404 KB Partially correct
20 Partially correct 87 ms 14992 KB Partially correct
21 Partially correct 91 ms 15032 KB Partially correct
22 Partially correct 84 ms 14288 KB Partially correct
23 Partially correct 90 ms 15196 KB Partially correct
24 Partially correct 83 ms 15052 KB Partially correct
25 Partially correct 93 ms 19180 KB Partially correct
26 Partially correct 79 ms 19200 KB Partially correct
27 Partially correct 95 ms 19400 KB Partially correct
28 Partially correct 86 ms 19356 KB Partially correct
29 Partially correct 81 ms 19188 KB Partially correct
30 Partially correct 83 ms 19188 KB Partially correct
31 Partially correct 80 ms 19196 KB Partially correct
32 Partially correct 87 ms 15212 KB Partially correct
33 Partially correct 83 ms 15044 KB Partially correct