답안 #524654

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
524654	2022-02-09T18:15:37 Z	amunduzbaev	Ancient Machine (JOI21_ancient_machine)	C++17	99 / 100	60 ms	8088 KB

Anna

#include "Anna.h"
#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
const int B = 90;
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;
	}
	//~ cout<<f<<" "<<n<<" "<<s[0]<<endl;
	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);
		}
	}
}

Bruno

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

#define ll long long
const int B = 90;

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

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	484 KB	Output is correct
2	Correct	0 ms	496 KB	Output is correct
3	Correct	0 ms	484 KB	Output is correct
4	Correct	0 ms	484 KB	Output is correct
5	Correct	0 ms	460 KB	Output is correct
6	Correct	0 ms	492 KB	Output is correct
7	Correct	0 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	484 KB	Output is correct
11	Correct	0 ms	484 KB	Output is correct

Subtask #2

94.0 / 95.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	59 ms	7812 KB	Partially correct
2	Partially correct	57 ms	7936 KB	Partially correct
3	Partially correct	52 ms	7876 KB	Partially correct
4	Partially correct	48 ms	7928 KB	Partially correct
5	Partially correct	52 ms	7928 KB	Partially correct
6	Partially correct	47 ms	7988 KB	Partially correct
7	Partially correct	47 ms	7992 KB	Partially correct
8	Partially correct	55 ms	7912 KB	Partially correct
9	Partially correct	49 ms	7896 KB	Partially correct
10	Partially correct	47 ms	8088 KB	Partially correct
11	Partially correct	48 ms	7944 KB	Partially correct
12	Partially correct	51 ms	7896 KB	Partially correct
13	Partially correct	56 ms	7964 KB	Partially correct
14	Partially correct	60 ms	8048 KB	Partially correct
15	Partially correct	49 ms	7964 KB	Partially correct
16	Partially correct	52 ms	8012 KB	Partially correct
17	Partially correct	57 ms	7968 KB	Partially correct
18	Correct	43 ms	6376 KB	Output is correct
19	Correct	46 ms	6428 KB	Output is correct
20	Partially correct	54 ms	8044 KB	Partially correct
21	Partially correct	47 ms	7960 KB	Partially correct
22	Partially correct	57 ms	8004 KB	Partially correct
23	Partially correct	51 ms	7888 KB	Partially correct
24	Partially correct	46 ms	7968 KB	Partially correct
25	Correct	43 ms	6432 KB	Output is correct
26	Partially correct	60 ms	7928 KB	Partially correct
27	Partially correct	60 ms	7948 KB	Partially correct
28	Partially correct	56 ms	7960 KB	Partially correct
29	Correct	45 ms	6488 KB	Output is correct
30	Partially correct	55 ms	7952 KB	Partially correct
31	Correct	43 ms	6384 KB	Output is correct
32	Partially correct	49 ms	7940 KB	Partially correct
33	Partially correct	53 ms	7996 KB	Partially correct