CSES - HIIT Open 2016 - Results
Submission details
Task:Fixed points
Sender:Game of Nolife
Submission time:2016-05-28 15:49:47 +0300
Language:C++
Status:READY
Result:
Test results
testverdicttime
#10.10 sdetails

Code

#include <bits/stdc++.h>
#define F first
#define S second
#define X real()
#define Y imag()
using namespace std;
typedef unsigned long long ll;
typedef long double ld;

ll mod = (1<<11);

int number_of_solutions(ll a, ll b) {
	int sol_count = 0;
	for (ll x = 0; x < mod; x++) {
		ll y = (a*x)^b;
		if (((y - x)%mod) == 0) {
			sol_count++;
		}
	}
	return sol_count;
}

int smallest_solution(ll a, ll b) {
	for (ll x = 0; x < mod; x++) {
		ll y = (a*x)^b;
		if (((y - x)%mod) == 0) {
			return x;
		}
	}
	return -1;
}

int biggest_solution(ll a, ll b) {
	for (ll x = mod - 1; x >= 0; x--) {
		ll y = (a*x)^b;
		if (((y - x)%mod) == 0) {
			return x;
		}
	}
	return -1;
}

ll go(ll x, ll a, ll b, ll i) {
	if ((((a*x)^b)-x)%((1 << i)) == 0) {
		if (i == 11) {
			return x;
		}
		ll y = go(x, a, b, i + 1);
		if (y > 0) {
			return y;
		} else {
			y = go(x + (1 << i), a, b, i + 1);
			if (y > 0) {
				return y;
			} else {
				return 0;
			}
		}
	}
	return 0;
}


int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin >> t;
	for (int tc = 0; tc < t; tc++) {
		ll a, b;
		cin >> a >> b;
		if (b == 0) {
			cout << "0\n";
		} else {
			ll x = go(0, a, b, 0);
			if (x == 0) {
				cout << "-\n";
			} else {
				cout << x << "\n";
			}
		}
	}
}

Test details

Test 1

Verdict:

input
100000
12865169357617740396 294321893...

correct output
5903494652862419412
-
13008184152928659765
9415006529485574473
16201136572240455608
...

user output
468
-
309
329
1976
...