Submission #575468

#	Time	Username	Problem	Language	Result	Execution time	Memory
575468		Arvin	Ancient Machine (JOI21_ancient_machine)	C++17	90 / 100	67 ms	9028 KiB

Anna

#include "Anna.h"
#include <bits/stdc++.h>
	
using namespace std;
	
#define ll long long
	
namespace {
	
int variable_example = 0;
	const int maxN = 1e5 + 5;	
}
	
struct SegmentTree {
	int tree[2*maxN];
	int n;
	
	void reset(){
		fill(tree, tree+2*maxN, 1e9);
	}
	
	void build(int n, vector<int> &v){
		this->n = n;
		for(int x=0;x<n;x++){
			tree[n+x] = v[x];
		}
		for(int x=n-1;x>0;x--){
			tree[x] = min(tree[x<<1], tree[x<<1|1]);
		}
	}
	
	void update(int pos, int val){
		pos += n;
	
		tree[pos] = val;
		for(int x=pos;x>1;x>>=1){
			tree[x>>1] = min(tree[x], tree[x^1]);
		}
	}
	
	int query(int left, int right){ // [L, R)
		int ans = 1e9;
		for(left += n, right += n; left < right; left >>= 1, right >>= 1){
			if(left&1){
				ans = min(ans, tree[left++]);
			}
			if(right&1){
				ans = min(ans, tree[--right]);
			}
		}
		return ans;
	}
} tree;
	
void Anna(int N, std::vector<char> S) {
	// 1 as store this first X or any Z after first Xa
	// 0 otherwise
	
	vector<int> v;
	int pos = -1;
	bool fX = false;
	for(int x=0;x<N;x++){
		if(S[x] == 'Z'){
			if(fX && (x+1 == N || S[x+1] != 'Z')){
				v.push_back(1);
			} else {
				v.push_back(0);
			}
			// Send(fX);
		} else if(S[x] == 'Y'){
			// Send(0);
			v.push_back(0);
		} else if(S[x] == 'X'){
			if(!fX){
				v.push_back(1);
				// Send(1);
				fX = true;
				pos = x;
			} else {
				v.push_back(0);
				// Send(0);
			}
		}
	}
	
	// guaranteed bit 1 at most N/2 + 1
	// alternating, only special case where first X and any Z are adjacent.

	// first 16 bits are location of first X
	// if not exist: ok delete all
	// else :
	// check first bit after loc
	// if 0 length is odd
	// - if one:
	// - - 
	// - else:

	for(int x=0;x<17;x++){
		if((pos+1)&(1 << x)){
			Send(1);
		} else {
			Send(0);
		}
	}
	
	// 1010
	// 1001
	// 0101
	// 1000
	// 0100
	// 0010
	// 0001
	// 0000
	
	map<int, int> mp;
	int cnt = 0;
	for(int x=0;x<16;x++){
		bool ok = true;
		int lst = -2;
		for(int y=0;y<4;y++){
			if(x&(1 << y)){
				if(y-lst <= 1){
					ok = false;
					break;
				}
				lst = y;
			}
		}
		
		if(ok){
			mp[x] = cnt++;
		}
	}
	
	if(pos != -1){
		for(int x=pos+1;x<N;x+=4){
			int state = 0;
			for(int y=0;y<4;y++){
				if(x+y >= N){
					continue;
				}
				
				if(v[x+y] == 1){
					state |= (1 << y);
				}
			}
			
			for(int y=0;y<3;y++){
				if(mp[state]&(1 << y)){
					Send(1);
				} else {
					Send(0);
				}
			}
		}
	}
	// Send(v[0]);
	// bool skip = false;
	// for(int x=0;x<N;x++){
	// 	if(skip){
	// 		skip = false;
	// 		continue;
	// 	}
	
	// 	if(v[x] == 0){
	// 		if(x+1 == N || v[x+1] == 1){
	// 			Send(0);
	// 			if(x+1 < N && v[x+1] == 1) Send(1);
	// 			else Send(0);
	// 		} else {
	// 			Send(1);
	// 			if(x+2 < N && v[x+2] == 1){
	// 				Send(1);
	// 			} else {
	// 				Send(0);
	// 			}
	// 			skip = true;
	// 		}
	// 	}
	// }
}

Bruno

#include "Bruno.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long

namespace {

int variable_example = 0;

int FunctionExample(int P) { return 1 - P; }

}  // namespace

void Bruno(int N, int L, std::vector<int> A) {
//	for (int i = 0; i < L; i++) {
//	variable_example += FunctionExample(A[i]);
//	}
	// assert(L <= N);
	

	// length >= 3, use 1 + log2(length) bits
	// length <= 2
//	for(auto val : A){
//		cout << val << " ";
//	}cout << "\n";
	vector<int> v(N, 0);
	int idx = 0;
	for(int x=0;x<17;x++){
		if(A[x] == 1){
			idx += (1 << x);
		}
	}
	
	if(idx == 0){
		for(int x=0;x<N;x++){
			Remove(x);
		}
		return;
	}
	
//	cout << idx << " =\n";
	idx--;
	v[idx] = 1;
	idx++;
	
	map<int, int> mp;
	int cnt = 0;
	for(int x=0;x<16;x++){
		bool ok = true;
		int lst = -2;
		for(int y=0;y<4;y++){
			if(x&(1 << y)){
				if(y-lst <= 1){
					ok = false;
					break;
				}
				lst = y;
			}
		}
		
		if(ok){
			mp[cnt++] = x;
		}
	}
	
	int pos = 17;
	while(pos < L){
		int state = 0;
		for(int y=0;y<3;y++){
			if(A[pos++] == 1){
				state += (1 << y);
			}
		}
		
		int val = mp[state];
		for(int y=0;y<4;y++){
			if(idx >= N) break;
			v[idx++] = ((val&(1 << y)) != 0);
		}
	}
	// for(auto val : v){
	// 	cout << val << "\n";
	// }
	// cout << v.size() << "\n";
	vector<int> ans;
	pos = -1;
	int lst = 0;
	for(int x=0;x<v.size();x++){
		if(v[x] == 1){
			if(pos == -1){
				pos = x;
				lst = x+1;
			} else {
				for(int y=x-1;y>=lst;y--){
					ans.push_back(y);
				}
				ans.push_back(x);
				lst = x+1;
			}
		}
	}
	
	for(int x=0;x<=pos;x++){
		ans.push_back(x);
	}
	for(int x=lst;x<N;x++){
		ans.push_back(x);
	}

	for(auto val : ans){
		// cout << "- " << val << "\n";
		Remove(val);
	}
}

Compilation message (stderr)

Anna.cpp:10:5: warning: '{anonymous}::variable_example' defined but not used [-Wunused-variable]
   10 | int variable_example = 0;
      |     ^~~~~~~~~~~~~~~~

Bruno.cpp: In function 'void Bruno(int, int, std::vector<int>)':
Bruno.cpp:90:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |  for(int x=0;x<v.size();x++){
      |              ~^~~~~~~~~
Bruno.cpp: At global scope:
Bruno.cpp:12:5: warning: 'int {anonymous}::FunctionExample(int)' defined but not used [-Wunused-function]
   12 | int FunctionExample(int P) { return 1 - P; }
      |     ^~~~~~~~~~~~~~~
Bruno.cpp:10:5: warning: '{anonymous}::variable_example' defined but not used [-Wunused-variable]
   10 | int variable_example = 0;
      |     ^~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 85 / 95