oj.uz

Submission #966464

# Submission time Handle Problem Language Result Execution time Memory
966464 2024-04-19T23:44:21 Z pavement Ancient Machine (JOI21_ancient_machine) C++17
5 / 100
 42 ms 7724 KB 
#include "Anna.h"
#include <bits/stdc++.h>
using namespace std;

using i128 = __int128;

#define pb push_back

const int BLK_SZ = 183;

void Anna(int N, vector<char> S) {
	int first_X = -1;
	vector<bool> positions(N);
	vector<i128> fib(BLK_SZ + 1);
	fib[0] = fib[1] = 1;
	for (int i = 2; i <= BLK_SZ; i++) {
		fib[i] = fib[i - 1] + fib[i - 2];
	}
	for (int i = 0; i < N; i++) {
		if (S[i] == 'X' && first_X == -1) {
			first_X = i;
		} else if (first_X == -1) {
			continue;
		} else if (S[i] == 'Z') {
			assert(i);
			if (positions[i - 1] == 1) {
				positions[i - 1] = 0;
			}
			positions[i] = 1;
		}
	}
	for (int i = 0; i < N; i += BLK_SZ) {
		int r = min(N, i + BLK_SZ);
		// [i, r)
		i128 cur = 0;
		for (int j = i; j < r; j++) {
			if (positions[j]) {
				cur += fib[r - j];
			}
		}
		for (int j = 0; j < 128; j++) {
			Send(!!(cur & ((i128)1 << j)));
		}
	}
	for (int j = 0; j < 17; j++) {
		Send(!!((first_X + 1) & ((i128)1 << j)));
	}
}

#include "Bruno.h"
#include <bits/stdc++.h>
using namespace std;

using i128 = __int128;

#define pb push_back

const int BLK_SZ = 183;

void Bruno(int N, int L, vector<int> A) {
	int first_X = 0;
	vector<bool> positions(N);
	vector<i128> fib(BLK_SZ + 1);
	fib[0] = fib[1] = 1;
	for (int i = 2; i <= BLK_SZ; i++) {
		fib[i] = fib[i - 1] + fib[i - 2];
	}
	for (int j = L - 17; j < L; j++) {
		if (A[j]) {
			first_X |= (1 << (j - (L - 17)));
		}
	}
	first_X--;
	if (first_X == -1) {
		for (int i = 0; i < N; i++) {
			Remove(i);
		}
		return;
	}
	for (int i = 0, l = 0; i < L - 17; i += 128, l += BLK_SZ) {
		int r = min(N, l + BLK_SZ);
		i128 cur = 0;
		for (int j = i; j < min(L, i + 128); j++) {
			if (A[j]) {
				cur |= ((i128)1 << (j - i));
			}
		}
		// [l, r)
		for (int j = l; j < r; j++) {
			if (fib[r - j] > cur) {
				positions[j] = 0;
			} else {
				positions[j] = 1;
				cur -= fib[r - j];
				j++;
			}
		}
	}
	for (int i = 0; i < first_X; i++) {
		Remove(i);
	}
	vector<int> buf;
	for (int i = first_X + 1; i < N; i++) {
		if (positions[i]) {
			while (!buf.empty()) {
				Remove(buf.back());
				buf.pop_back();
			}
			Remove(i);
		} else {
			buf.pb(i);
		}
	}
	buf.pb(first_X);
	while (!buf.empty()) {
		Remove(buf.back());
		buf.pop_back();
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 788 KB Output is correct
2 Correct 0 ms 792 KB Output is correct
3 Correct 0 ms 792 KB Output is correct
4 Correct 0 ms 792 KB Output is correct
5 Correct 0 ms 780 KB Output is correct
6 Correct 1 ms 1040 KB Output is correct
7 Correct 1 ms 792 KB Output is correct
8 Correct 1 ms 792 KB Output is correct
9 Correct 0 ms 780 KB Output is correct
10 Correct 0 ms 780 KB Output is correct
11 Correct 0 ms 792 KB Output is correct

Subtask #2
0 / 95.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 7724 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -