oj.uz

Submission #524656

# Submission time Handle Problem Language Result Execution time Memory
524656 2022-02-09T18:16:17 Z amunduzbaev Ancient Machine (JOI21_ancient_machine) C++17
5 / 100
 49 ms 8112 KB 
#include "Anna.h"
#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
const int B = 91;
ll dp[B][2];

void Anna(int n, vector<char> s) {
	int f = -1;
	for(int i=0;i<n;i++){
		if(s[i] == 'X') { f = i; break; }
	}
	
	int C = (n + B - 1) / B;
	if(f == -1){
		return;
	}
	
	for(int i=0;i<17;i++) Send(f >> i & 1);
	
	vector<int> res(n);
	//~ res[f] = 1;
	for(int i=f+1;i<n;i++){
		if(s[i] == 'Z'){
			res[i] = 1;
			if(s[i-1] == 'Z') res[i-1] = 0;
		}
	}
	
	dp[0][0] = dp[0][1] = 1;
	for(int i=1;i<B;i++){
		dp[i][0] = dp[i-1][0] + dp[i-1][1];
		dp[i][1] = dp[i-1][0];
	}
	
	//~ auto get = [&](vector<int> x) {
		//~ ii res = (ii)0;
		//~ for(int i=0;i<(int)x.size();i++){
			//~ if(x[i]) res += dp[i][0];
		//~ } return res;
	//~ };
	//~ for(int i=0;i<n;i++) cout<<res[i]<<" ";
	//~ cout<<"\n";
	
	vector<int> rr;
	for(int i=0;i<C;i++){
		vector<int> tmp = vector<int>(res.begin() + i * B, res.begin() + min(n, (i + 1) * B));
		ll v = 0;
		for(int i=0;i<(int)tmp.size();i++){
			if(tmp[i]) v = v + dp[i][0];
		} 
		
		for(int j=0;j<63;j++){
			Send(v >> j & 1);
		}
	}
}

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

#define ll long long
const int B = 91;

void Bruno(int n, int l, vector<int> a) {
	ll dp[B][2] {};
	dp[0][0] = dp[0][1] = 1;
	for(int i=1;i<B;i++){
		dp[i][0] = dp[i-1][0] + dp[i-1][1];
		dp[i][1] = dp[i-1][0];
	}
	//~ cout<<n<<" "<<l<<endl;
	if(!l){
		for(int i=0;i<n;i++) Remove(i);
		return;
	}
	
	int f = 0;
	for(int i=0;i<17;i++) f |= (a[i] << i);
	a.erase(a.begin(), a.begin() + 17);
	//~ cout<<f<<endl;
	
	int C = (n + B - 1) / B;
	vector<int> is(C * B);
	for(int i=0;i<C;i++){
		ll v = 0;
		for(int j=i*63;j<(i+1)*63;j++){
			v |= ((a[j] * 1ll) << (j - i*63));
		}
		
		for(int l=B-1;~l;l--){
			if(v >= dp[l][0]) is[i * B + l] = 1, v -= dp[l][0];
		}
		
		//~ cout<<"here"<<endl;
	}
	
	for(int i=0;i<f;i++) Remove(i);
	int last = f; //, f = -1;
	for(int i=f+1;i<n;i++){
		if(is[i]){
			int j = i - 1;
			while(j > last) Remove(j--);
			Remove(i); last = i;
		}
	}
	
	int j = n - 1;
	while(j > last) Remove(j--);
	Remove(f);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 95.0

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