Submission #2359769

---

Source Code Expand

#include <stdio.h>
#include <algorithm>
using namespace std;

struct matrix{
	matrix(){
		for (int i=0;i<36;i++) for (int j=0;j<36;j++) a[i][j] = 0;
	}
	bool a[36][36];

	matrix operator *(matrix t){
		matrix r;
		for (int i=0;i<36;i++) for (int j=0;j<36;j++) for (int k=0;k<36;k++) if (a[i][k] & t.a[k][j])
			r.a[i][j] ^= 1;
		return r;
	}
};

struct data{
	long long a, l, pos;
	bool operator <(const data &t)const{
		if (a != t.a) return a < t.a;
		return l == -1 ? pos > t.pos : pos < t.pos;
	}
}P[1<<18],Q[1<<18];

int bc[1<<18];

int main()
{
	for (int i=1;i<(1<<18);i++){
		int x = i & (-i);
		bc[i] = bc[i-x] + 1;
	}

	long long A,B,X,T; scanf ("%lld %lld %lld",&A,&B,&X);

	matrix b[19];
	for (int i=0;i<35;i++) b[0].a[i][i+1] = 1;
	for (int i=0;i<36;i++) if (B & (1ll << i)) b[0].a[i][0] = 1;
	for (int i=1;i<=18;i++) b[i] = b[i-1] * b[i-1];

	long long BC[19][36] = {0,};
	for (int k=0;k<=18;k++){
		for (int i=0;i<36;i++) for (int j=0;j<36;j++) if (b[k].a[i][j]) BC[k][i] |= 1ll << j;
	}

	auto nxt = [&](int k, long long x){
		long long n = 0;
		for (int i=0;i<36;i++){
			long long o = BC[k][i] & x;
			if ((bc[o>>18] + bc[o%(1<<18)]) % 2) n |= 1ll << i;
		}
		return n;
	};

	T = X;
	for (int i=0;i<(1<<18);i++){
		long long n = nxt(0,T);
		P[i] = {n,-1,i+1};
		T = n;
	}

	for (int i=0;i<(1<<18);i++){
		long long n = nxt(18,A);
		Q[i] = {n,A,(1ll<<18)*(i+1)};
		A = n;
	}

	sort(P,P+(1<<18));
	sort(Q,Q+(1<<18));

	long long ans = 1e18;
	int i = 0, j = 0;
	while (i < (1<<18) && j < (1<<18)){
		if (P[i].a < Q[j].a) i++;
		else if (P[i].a > Q[j].a) j++;
		else{
			long long a = P[i].a;

			long long st[2],pos[2]; int c = 1;
			st[0] = Q[j].l;
			pos[0] = Q[j].pos;
			j++;
			if (j < (1<<18) && Q[j].a == a){
				st[1] = Q[j].l;
				pos[1] = Q[j].pos;
				c++;
			}

			while (i < (1<<18) && P[i].a == a){
				for (int t=0;t<c;t++) if (ans > pos[t] - P[i].pos){
					long long v = st[t];
					int mv = (1<<18) - P[i].pos;
					for (int k=0;k<18;k++) if (mv & (1 << k)) v = nxt(k,v);

					if (v == X)
						ans = pos[t] - P[i].pos;
				}
				i++;
			}
		}
	}
	if (ans > 1e17) ans = -1;

	printf ("%lld\n",ans);

	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:36:54: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  long long A,B,X,T; scanf ("%lld %lld %lld",&A,&B,&X);
                                                      ^

Judge Result