Submission #2359615


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, pos;
	bool operator <(const data &t)const{
		if (a != t.a) return a < t.a;
		return 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[x] = bc[i-x] + 1;
	}

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

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

	long long BC[36] = {0,};
	for (int i=0;i<36;i++) for (int j=0;j<36;j++) if (b.a[i][j]) BC[i] |= 1ll << j;
	for (int i=0;i<(1<<18);i++){
		long long n = 0;
		for (int i=0;i<36;i++){
			long long o = BC[i] & X;
			if ((bc[o>>18] + bc[o%(1<<18)]) % 2) n |= 1ll << i;
		}
		P[i] = {X=n,i+1};
	}

	for (int i=0;i<18;i++) b = b * b;
	for (int i=0;i<36;i++){
		BC[i] = 0;
		for (int j=0;j<36;j++) if (b.a[i][j]) BC[i] |= 1ll << j;
	}
	for (int i=0;i<(1<<18);i++){
		long long n = 0;
		for (int i=0;i<36;i++){
			long long o = BC[i] & A;
			if ((bc[o>>18] + bc[o%(1<<18)]) % 2) n |= 1ll << i;
		}
		Q[i] = {A=n,(1ll<<18)*(i+1)};
	}

	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{
			if (ans > Q[j].pos - P[i].pos)
				ans = Q[j].pos - P[i].pos;
			i++;
		}
	}
	if (ans > 1e17) ans = -1;

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

	return 0;
}

Submission Info

Submission Time
Task K - 乱数調整
User august14
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1813 Byte
Status WA
Exec Time 140 ms
Memory 8448 KB

Compile Error

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

Judge Result

Set Name Subtask All
Score / Max Score 0 / 30 0 / 270
Status
AC × 8
WA × 12
AC × 19
WA × 44
Set Name Test Cases
Subtask subtask_00.txt, subtask_01.txt, subtask_02.txt, subtask_03.txt, subtask_04.txt, subtask_05.txt, subtask_06.txt, subtask_07.txt, subtask_08.txt, subtask_09.txt, subtask_10.txt, subtask_11.txt, subtask_12.txt, subtask_13.txt, subtask_14.txt, subtask_15.txt, subtask_16.txt, subtask_17.txt, subtask_18.txt, subtask_19.txt
All scrambled_00.txt, scrambled_01.txt, scrambled_02.txt, scrambled_03.txt, scrambled_04.txt, scrambled_05.txt, scrambled_06.txt, scrambled_07.txt, scrambled_08.txt, scrambled_09.txt, scrambled_10.txt, scrambled_11.txt, scrambled_12.txt, scrambled_13.txt, scrambled_14.txt, scrambled_15.txt, scrambled_16.txt, scrambled_17.txt, scrambled_18.txt, scrambled_19.txt, scrambled_20.txt, scrambled_21.txt, scrambled_22.txt, scrambled_23.txt, scrambled_24.txt, scrambled_25.txt, scrambled_26.txt, scrambled_27.txt, scrambled_28.txt, scrambled_29.txt, scrambled_30.txt, scrambled_31.txt, scrambled_32.txt, scrambled_33.txt, scrambled_34.txt, scrambled_35.txt, scrambled_36.txt, scrambled_37.txt, scrambled_38.txt, scrambled_39.txt, scrambled_40.txt, scrambled_41.txt, scrambled_42.txt, subtask_00.txt, subtask_01.txt, subtask_02.txt, subtask_03.txt, subtask_04.txt, subtask_05.txt, subtask_06.txt, subtask_07.txt, subtask_08.txt, subtask_09.txt, subtask_10.txt, subtask_11.txt, subtask_12.txt, subtask_13.txt, subtask_14.txt, subtask_15.txt, subtask_16.txt, subtask_17.txt, subtask_18.txt, subtask_19.txt
Case Name Status Exec Time Memory
scrambled_00.txt AC 82 ms 8448 KB
scrambled_01.txt AC 83 ms 8448 KB
scrambled_02.txt AC 73 ms 8448 KB
scrambled_03.txt AC 63 ms 8448 KB
scrambled_04.txt WA 102 ms 8448 KB
scrambled_05.txt WA 119 ms 8448 KB
scrambled_06.txt WA 93 ms 8448 KB
scrambled_07.txt WA 112 ms 8448 KB
scrambled_08.txt WA 75 ms 8448 KB
scrambled_09.txt WA 91 ms 8448 KB
scrambled_10.txt WA 96 ms 8448 KB
scrambled_11.txt WA 118 ms 8448 KB
scrambled_12.txt WA 118 ms 8448 KB
scrambled_13.txt WA 120 ms 8448 KB
scrambled_14.txt AC 127 ms 8448 KB
scrambled_15.txt AC 137 ms 8448 KB
scrambled_16.txt AC 102 ms 8448 KB
scrambled_17.txt AC 139 ms 8448 KB
scrambled_18.txt WA 117 ms 8448 KB
scrambled_19.txt WA 115 ms 8448 KB
scrambled_20.txt WA 117 ms 8448 KB
scrambled_21.txt WA 117 ms 8448 KB
scrambled_22.txt WA 107 ms 8448 KB
scrambled_23.txt WA 97 ms 8448 KB
scrambled_24.txt WA 117 ms 8448 KB
scrambled_25.txt WA 137 ms 8448 KB
scrambled_26.txt WA 124 ms 8448 KB
scrambled_27.txt WA 140 ms 8448 KB
scrambled_28.txt WA 55 ms 8448 KB
scrambled_29.txt WA 79 ms 8448 KB
scrambled_30.txt AC 56 ms 8448 KB
scrambled_31.txt AC 82 ms 8448 KB
scrambled_32.txt WA 55 ms 8448 KB
scrambled_33.txt WA 60 ms 8448 KB
scrambled_34.txt AC 127 ms 8448 KB
scrambled_35.txt WA 87 ms 8448 KB
scrambled_36.txt WA 93 ms 8448 KB
scrambled_37.txt WA 70 ms 8448 KB
scrambled_38.txt WA 88 ms 8448 KB
scrambled_39.txt WA 105 ms 8448 KB
scrambled_40.txt WA 81 ms 8448 KB
scrambled_41.txt WA 105 ms 8448 KB
scrambled_42.txt WA 105 ms 8448 KB
subtask_00.txt AC 97 ms 8448 KB
subtask_01.txt AC 96 ms 8448 KB
subtask_02.txt WA 109 ms 8448 KB
subtask_03.txt AC 85 ms 8448 KB
subtask_04.txt WA 89 ms 8448 KB
subtask_05.txt WA 106 ms 8448 KB
subtask_06.txt WA 101 ms 8448 KB
subtask_07.txt WA 78 ms 8448 KB
subtask_08.txt AC 104 ms 8448 KB
subtask_09.txt AC 108 ms 8448 KB
subtask_10.txt WA 104 ms 8448 KB
subtask_11.txt AC 118 ms 8448 KB
subtask_12.txt WA 106 ms 8448 KB
subtask_13.txt WA 103 ms 8448 KB
subtask_14.txt WA 55 ms 8448 KB
subtask_15.txt WA 79 ms 8448 KB
subtask_16.txt AC 56 ms 8448 KB
subtask_17.txt AC 55 ms 8448 KB
subtask_18.txt WA 55 ms 8448 KB
subtask_19.txt WA 60 ms 8448 KB