Submission #398155

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
398155	2021-05-03T20:11:50 Z	ChrisT	Ancient Machine (JOI21_ancient_machine)	C++17	40 / 100	131 ms	9068 KB

Anna

#include <bits/stdc++.h>
#include "Anna.h"
using namespace std;
const int MN = 1e6 + 5;
map<char,int> gg = {{'X',0},{'Y',1},{'Z',2}};	
void Anna (int n, vector<char> s) {
	for (int i = 0; i < n; i += 29) {
		//[i,i+29)
		int ed = min(i+29,n);
		long long val = 0, pw = 1;
		for (int j = i; j < ed; j++) {
			val += pw * gg[s[j]];
			pw *= 3;
		}
		for (int j = 0; j < 46; j++) Send(val >> j & 1);
	}
}

Bruno

#include <bits/stdc++.h>
#include "Bruno.h"
using namespace std;
const int MN = 1e6 + 5;
map<int,char> gg = {{0,'X'},{1,'Y'},{2,'Z'}};
void Bruno (int n, int l, vector<int> a) {
	vector<char> s(n); reverse(a.begin(),a.end());
	for (int i = 0; i < n; i += 29) {
		int ed = min(i+29,n); long long val = 0;
		for (int j = 0; j < 46; j++) {
			val |= (((long long)a.back()) << j);
			a.pop_back();
		}
		for (int j = i; j < ed; j++) {
			s[j] = gg[val % 3];
			val /= 3;
		}
	}
	int st = 0;
	while (st < n && s[st] != 'X') Remove(st++);
	if (st == n) return;
	int ed = n-1;
	while (ed >= st && s[ed] != 'Z') Remove(ed--);
	vector<int> inds = {st}; bool found = false;
	vector<bool> dead(n);
	for (int i = st+1; i <= ed; i++) {
		if (s[i] != 'Y') Remove(i), dead[i] = true;
		else {
			found = true;
			break;
		}
	}
	if (!found) return;
	for (int i = ed-1; i >= st; i--) {
		if (s[i] != 'Y') Remove(i), dead[i] = true;
		else break;
	}
	for (int i = st + 1; i <= ed - 1; i++) {
		if (!dead[i] && !dead[i-1] && (s[i] == 'Y') == (s[i-1] == 'Y')) Remove(i-1), dead[i-1] = true;
	}
	set<int> xs,ys,zs;
	for (int i = st; i <= ed; i++) if (!dead[i]) {
		if (s[i] == 'X') xs.insert(i);
		else if (s[i] == 'Y') ys.insert(i);
		else zs.insert(i);
	}
	while (!ys.empty()) {
		int fz = *zs.begin();
		int lx = *prev(xs.upper_bound(fz));
		int my = *ys.lower_bound(lx);
		assert(lx <= my && my <= fz);
		Remove(my); ys.erase(my);
		if (fz != ed) Remove(fz), zs.erase(fz);
		else Remove(lx), xs.erase(lx);
	}
	for (int i : xs) Remove(i);
	for (int i : zs) Remove(i);
}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	484 KB	Output is correct
2	Correct	2 ms	484 KB	Output is correct
3	Correct	2 ms	492 KB	Output is correct
4	Correct	2 ms	484 KB	Output is correct
5	Correct	2 ms	484 KB	Output is correct
6	Correct	2 ms	492 KB	Output is correct
7	Correct	2 ms	480 KB	Output is correct
8	Correct	2 ms	484 KB	Output is correct
9	Correct	2 ms	484 KB	Output is correct
10	Correct	2 ms	492 KB	Output is correct
11	Correct	2 ms	484 KB	Output is correct

Subtask #2

35.0 / 95.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	105 ms	8764 KB	Partially correct
2	Partially correct	98 ms	8768 KB	Partially correct
3	Partially correct	98 ms	8764 KB	Partially correct
4	Partially correct	97 ms	8776 KB	Partially correct
5	Partially correct	129 ms	8720 KB	Partially correct
6	Partially correct	96 ms	8828 KB	Partially correct
7	Partially correct	98 ms	8684 KB	Partially correct
8	Partially correct	96 ms	8796 KB	Partially correct
9	Partially correct	103 ms	8792 KB	Partially correct
10	Partially correct	99 ms	8824 KB	Partially correct
11	Partially correct	96 ms	8780 KB	Partially correct
12	Partially correct	127 ms	8776 KB	Partially correct
13	Partially correct	117 ms	8888 KB	Partially correct
14	Partially correct	111 ms	8788 KB	Partially correct
15	Partially correct	97 ms	8792 KB	Partially correct
16	Partially correct	102 ms	8760 KB	Partially correct
17	Partially correct	95 ms	8596 KB	Partially correct
18	Partially correct	95 ms	8624 KB	Partially correct
19	Partially correct	109 ms	8536 KB	Partially correct
20	Partially correct	109 ms	8916 KB	Partially correct
21	Partially correct	114 ms	9068 KB	Partially correct
22	Partially correct	83 ms	8660 KB	Partially correct
23	Partially correct	111 ms	8728 KB	Partially correct
24	Partially correct	102 ms	8732 KB	Partially correct
25	Partially correct	96 ms	8676 KB	Partially correct
26	Partially correct	112 ms	8696 KB	Partially correct
27	Partially correct	114 ms	8648 KB	Partially correct
28	Partially correct	87 ms	8584 KB	Partially correct
29	Partially correct	95 ms	8540 KB	Partially correct
30	Partially correct	97 ms	8652 KB	Partially correct
31	Partially correct	101 ms	8536 KB	Partially correct
32	Partially correct	111 ms	8780 KB	Partially correct
33	Partially correct	131 ms	8856 KB	Partially correct