Submission #1226696

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226696		emptypringlescan	Broken Device (JOI17_broken_device)	C++17	0 / 100	20 ms	1432 KiB

Anna

#include "Annalib.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
long long memo[2][100];
long long num(int x, int cur){
	if(x==0) return 1;
	if(memo[cur][x]!=-1) return memo[cur][x];
	if(cur==0) return memo[cur][x]=num(x-1,1);
	else return memo[cur][x]=num(x-1,0)+num(x-1,1);
}
vector<int> lexi(long long x){
	vector<int> ret={1};
	for(int i=0; i<90; i++){
		if(ret.back()==1){
			if(num(90-i-1,0)>=x){
				ret.push_back(0);
			}
			else{
				ret.push_back(1);
				x-=num(90-i-1,0);
			}
		}
		else{
			ret.push_back(1);
		}
	}
	return ret;
}
long long rev(vector<int> x){
	long long ret=0;
	for(int i=1; i<91; i++){
		if(x[i]==1&&x[i-1]==1) ret+=num(90-i,0);
	}
	return ret+1;
}
}
void Anna( int N, long long X, int K, int P[] ){
	for(int i=0; i<2; i++) for(int j=0; j<100; j++) memo[i][j]=-1;
	vector<int> yey=lexi(X+1);
	vector<int> ans(150);
	for(int i=0; i<150; i++) ans[i]=-1;
	for(int i=0; i<K; i++) ans[P[i]]=0;
	int cur=0,wrote=1;
	for(int i=0; i<150; i++){
		if(cur==91) break;
		if(ans[i]==0) wrote^=1;
		else{
			if(wrote!=yey[cur]) ans[i]=0,wrote^=1;
			else ans[i]=1,cur++,wrote=1;
		}
	}
	for(int i=0; i<N; i++) Set(i,max(ans[i],0));
}

Bruno

#include "Brunolib.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
long long memo[2][100];
long long num(int x, int cur){
	if(x==0) return 1;
	if(memo[cur][x]!=-1) return memo[cur][x];
	if(cur==0) return memo[cur][x]=num(x-1,1);
	else return memo[cur][x]=num(x-1,0)+num(x-1,1);
}
vector<int> lexi(long long x){
	vector<int> ret={1};
	for(int i=0; i<90; i++){
		if(ret.back()==1){
			if(num(90-i-1,0)>=x){
				ret.push_back(0);
			}
			else{
				ret.push_back(1);
				x-=num(90-i-1,0);
			}
		}
		else{
			ret.push_back(1);
		}
	}
	return ret;
}
long long rev(vector<int> x){
	long long ret=0;
	for(int i=1; i<91; i++){
		if(x[i]==1&&x[i-1]==1) ret+=num(90-i,0);
	}
	return ret+1;
}
}
long long Bruno( int N, int A[] ){
	for(int i=0; i<2; i++) for(int j=0; j<100; j++) memo[i][j]=-1;
	vector<int> yey={1};
	for(int i=0; i<N; i++){
		if(A[i]==0) yey.back()^=1;
		else yey.push_back(1);
	}
	while(yey.size()>91) yey.pop_back();
	return rev(yey);
}

• Subtask 1: 0 / 100