Submission #1101556

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101556		thelonewolf	Lamps (JOI19_lamps)	C++17	0 / 100	289 ms	262144 KiB

lamp

#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define fi first
#define se second
#define pir pair<int,int>
using namespace std;
const int maxn = 1e6 + 5;

struct CTDL{
	int state = 0,lst = 0,val = 0,l = 0,r = 0;
	char type = 0;
};

bool mark[maxn];
char type[maxn];
pir LR[maxn];
int dp[maxn],trace[maxn];
bool a[maxn],b[maxn];

int sum(int l,int r){
	if (l > r) return 0;
	return (1 << (r + 1)) - (1 << l);
}

void solve(int n){
	int Mask = 0;
	for (int i = 0 ; i < n ; i++)
	  if (a[i]) Mask += (1 << i);
	
	deque <CTDL> dq;
	dq.push_back({Mask,0,0,0,0,0});
	
	while (dq.size()){
		CTDL tmp = dq.front();
		dq.pop_front();
		
		int mask = tmp.state,d = tmp.val,prv = tmp.lst;
		
		if (mark[mask]) continue;
		trace[mask] = prv;
		LR[mask] = {tmp.l,tmp.r};
		type[mask] = tmp.type;
		mark[mask] = 1;
		dp[mask] = d;
		
		for (int i = 0 ; i < n ; i++)
		  for (int j = i ; j < n ; j++){
		  	//and 0
		  	int a0 = sum(0,n - 1) - sum(i,j);
		  	int submask = mask & a0;
		  	
		  	dq.push_back({submask,mask,d + 1,i,j,'&'});
		  	
		  	
		  	//or 1
		  	a0 ^= sum(0,n - 1);
		  	submask = mask | a0;
		  	dq.push_back({submask,mask,d + 1,i,j,'|'});
		  	
		  	//xor 1
		    submask = mask ^ a0;
		  	dq.push_back({submask,mask,d + 1,i,j,'^'});
		  }
	}
}

void input(int n){
	string s;
	cin >> s;
	
	for (int i = 0 ; i < n ; i++)
	  a[i] = s[i] - 48;
	
	cin >> s;
	for (int i = 0 ; i < n ; i++)
	  b[i] = s[i] - 48;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	int n;
	cin >> n;
	input(n);
	
	solve(n);
	
	int mask = 0;
	for (int i = 0 ; i < n ; i++)
	  if (b[i]) mask += (1 << i);
	
	/*cout << "TRACING" << "\n";
	vector <int> vec;
	while (mask){
		vec.push_back(mask);
		
		mask = trace[mask];
	}
	reverse(vec.begin(),vec.end());
	
	for (int mask : vec){
		cout << LR[mask].fi << " " << LR[mask].se << " " << type[mask] << endl;
		
		for (int i = 0 ; i < n ; i++)
		  cout << (((1 << i) & mask) > 0) ? 1 : 0;
		cout << "\n" << "\n";
	}*/
	
	cout << dp[mask];

	return 0;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 41
• Subtask 3: 0 / 4
• Subtask 4: 0 / 49