Submission #458881

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
458881	2021-08-08T06:43:13 Z	8e7	Ancient Machine (JOI21_ancient_machine)	C++17	100 / 100	69 ms	7992 KB

Anna

//Challenge: Accepted
#include "Anna.h"
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;

#define ll long long
#define maxn 100005
#define pii pair<int, int>
#define ff first
#define ss second

namespace{
	ll fib[65];
}

void Anna(int N, vector<char> S) {
	fib[0] = fib[1] = 1;
	for (int i = 2;i < 64;i++) fib[i] = fib[i - 1] + fib[i - 2];	
	vector<int> bit (N, 0);
	bool found = 0;
	int first = 0;
	for (int i = 0;i < N;i++) {
		if (S[i] == 'X' && !found) {
			found = 1;
			first = i;
			bit[i] = 1;
		}
		if (found && first != i - 1 && S[i] == 'Z' && (i == N - 1 || S[i + 1] != 'Z')) {
			bit[i] = 1;
		}	
	}
	for (int i = 0;i < N;i+=63){
		ll send = 0;
		for (int j = 0;j < 63;j++) send += fib[j+1] * (i + j < N ? bit[i+j] : 0);
		for (int j = 0;j < 44;j++) {
			Send((send & (1LL<<j)) ? 1 : 0);
		}
	}	
	if (found && first < N - 1 && S[first + 1] == 'Z') Send(1);
	else Send(0);
}
/*
g++ -std=gnu++17 -O2 -fsigned-char -o grader grader.cpp Anna.cpp Bruno.cpp
*/

Bruno

//Challenge: Accepted
#include "Bruno.h"
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b ...);};
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#define ll long long
#define maxn 100005
#define pii pair<int, int>
#define ff first
#define ss second


namespace {
	ll fib[65];

}  // namespace

void Bruno(int N, int L, vector<int> A) {
	fib[0] = fib[1] = 1;
	for (int i = 2;i < 64;i++) fib[i] = fib[i - 1] + fib[i - 2];	

	vector<int> v;
	for (int i = 0;i < L - 1;i += 44) {
		ll num = 0;
		for (int j = 0;j < 44;j++) num += ((ll)A[i+j])<<j;
		vector<int> tmp;
		for (int j = 63;j > 0;j--) {
			if (num >= fib[j]) {
				num -= fib[j];
				tmp.push_back(1);
			} else{
				tmp.push_back(0);	
			}
		}
		reverse(tmp.begin(), tmp.end());
		v.insert(v.end(), tmp.begin(), tmp.end());
	}	
	int ch = A.back();
	bool found = 0;
	int first = 0;
	for (int i = 0;i < N;i++) {
		if (v[i]) {
			for (int j = i - 1;j >= 0;j--) {
				if (v[j]) break;
				Remove(j);
			}
			if (!found) found = 1, first = i;
			else Remove(i);
		} else if (found && ch && i == first + 1) {
			Remove(i);
			v[i] = 1;
		}
	}
	for (int j = N - 1;j >= 0;j--) {
		if (v[j]) break;
		Remove(j);
	}
	if (found) Remove(first);
}
/*
5
X Y Z Y Z
*/

Subtask #1

5.0 / 5.0

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

Subtask #2

95.0 / 95.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	67 ms	7992 KB	Output is correct
2	Correct	59 ms	7904 KB	Output is correct
3	Correct	65 ms	7900 KB	Output is correct
4	Correct	59 ms	7844 KB	Output is correct
5	Correct	59 ms	7892 KB	Output is correct
6	Correct	59 ms	7832 KB	Output is correct
7	Correct	60 ms	7960 KB	Output is correct
8	Correct	59 ms	7956 KB	Output is correct
9	Correct	60 ms	7848 KB	Output is correct
10	Correct	60 ms	7840 KB	Output is correct
11	Correct	57 ms	7860 KB	Output is correct
12	Correct	59 ms	7948 KB	Output is correct
13	Correct	65 ms	7892 KB	Output is correct
14	Correct	66 ms	7908 KB	Output is correct
15	Correct	66 ms	7872 KB	Output is correct
16	Correct	67 ms	7932 KB	Output is correct
17	Correct	67 ms	7928 KB	Output is correct
18	Correct	66 ms	7796 KB	Output is correct
19	Correct	65 ms	7844 KB	Output is correct
20	Correct	59 ms	7876 KB	Output is correct
21	Correct	57 ms	7876 KB	Output is correct
22	Correct	69 ms	7840 KB	Output is correct
23	Correct	59 ms	7968 KB	Output is correct
24	Correct	60 ms	7864 KB	Output is correct
25	Correct	65 ms	7908 KB	Output is correct
26	Correct	65 ms	7784 KB	Output is correct
27	Correct	64 ms	7940 KB	Output is correct
28	Correct	64 ms	7896 KB	Output is correct
29	Correct	64 ms	7868 KB	Output is correct
30	Correct	66 ms	7912 KB	Output is correct
31	Correct	67 ms	7860 KB	Output is correct
32	Correct	59 ms	7864 KB	Output is correct
33	Correct	62 ms	7848 KB	Output is correct