Submission #2289251


Source Code Expand

Copy
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>

#define int long long
#define MOD7 1000000007
#define MOD9 1000000009

#define rep(i, n) for (int i = 0; i < (n); i++)
#define itrep(i, a) for (auto i = (a).begin(); i != (a).end(); i++)
#define REP(i, a, n) for (int i = (a); i <= (n); i++)
#define all(a) (a).begin(), (a).end()
#define mp(a, b) make_pair((a), (b))

using namespace std;

int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, -1, 0, 1 };

template<class T> void inputVector(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < v.size(); i++) cin >> v[i];
}

set<int> paths[55][55];

unsigned long long getCycle() {
	unsigned int low, high;
	__asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));
	return ((unsigned long long)low) | ((unsigned long long)high << 32);
}

long long beginCycle;
double getTime() {
	return (double)(getCycle() - beginCycle) / 2500000000;
}


signed main() {
	beginCycle = getCycle();

	int N;
	cin >> N;

	vector<int> a, b;
	inputVector(a, N);
	inputVector(b, N);

	rep(i, 51) {
		paths[i][i].insert(0);
	}

	REP(i, 1, 50) { // from
		rep(j, i) { // target
			REP(k, 1, i) { // mod
				int cost = 1LL << k;
				set<int> prepath = paths[i % k][j];
				itrep(it, prepath) {
					paths[i][j].insert(*it + cost);
				}
			}
		}
	}

	//rep(i, N) {
	//	cerr << "path " << i << ":";
	//	itrep(it, paths[a[i]][b[i]]) {
	//		cerr << " " << *it;
	//	}
	//	cerr << endl;
	//}

	int minVal = 0;
	rep(i, N) {
		int val = *paths[a[i]][b[i]].begin();
		int pw = 1;
		while (val >= pw) pw <<= 1;
		pw >>= 1;
		minVal = max(pw, minVal);
	}

	bool ans = false;
	int cnt = 0;
	for (int cost = minVal; cost < (1LL << 38); cost += 2) {
		bool ok = true;
		rep(i, N) {
			bool flag = false;
			itrep(it, paths[a[i]][b[i]]) {
				if ((*it & cost) == *it) {
					flag = true;
					break;
				}
			}
			if (!flag) {
				ok = false;
				break;
			}
		}
		if (ok) {
			cout << cost << endl;
			ans = true;
			break;
		}

		if ((cnt % 1000) == 0 && getTime() >= 1.8) break;
	}

	if (!ans) {
		cout << -1 << endl;
	}

    return 0;
}

Submission Info

Submission Time
Task C - Remainder Game
User iwashi31
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2446 Byte
Status
Exec Time 1613 ms
Memory 1536 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 s1.txt, s2.txt, s3.txt, s4.txt, s5.txt
All 0 / 700 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt, 51.txt, 52.txt, 53.txt, s1.txt, s2.txt, s3.txt, s4.txt, s5.txt
Case Name Status Exec Time Memory
01.txt 6 ms 1536 KB
02.txt 1613 ms 1536 KB
03.txt 6 ms 1536 KB
04.txt 6 ms 1536 KB
05.txt 581 ms 1536 KB
06.txt 6 ms 1536 KB
07.txt 6 ms 1536 KB
08.txt 1613 ms 1536 KB
09.txt 1613 ms 1536 KB
10.txt 1613 ms 1536 KB
11.txt 1613 ms 1536 KB
12.txt 6 ms 1536 KB
13.txt 6 ms 1536 KB
14.txt 1613 ms 1536 KB
15.txt 101 ms 1536 KB
16.txt 317 ms 1536 KB
17.txt 45 ms 1536 KB
18.txt 1613 ms 1536 KB
19.txt 1613 ms 1536 KB
20.txt 1613 ms 1536 KB
21.txt 1613 ms 1536 KB
22.txt 1613 ms 1536 KB
23.txt 1613 ms 1536 KB
24.txt 6 ms 1536 KB
25.txt 6 ms 1536 KB
26.txt 6 ms 1536 KB
27.txt 6 ms 1536 KB
28.txt 6 ms 1536 KB
29.txt 6 ms 1536 KB
30.txt 6 ms 1536 KB
31.txt 6 ms 1536 KB
32.txt 6 ms 1536 KB
33.txt 6 ms 1536 KB
34.txt 6 ms 1536 KB
35.txt 6 ms 1536 KB
36.txt 6 ms 1536 KB
37.txt 6 ms 1536 KB
38.txt 6 ms 1536 KB
39.txt 6 ms 1536 KB
40.txt 6 ms 1536 KB
41.txt 6 ms 1536 KB
42.txt 6 ms 1536 KB
43.txt 6 ms 1536 KB
44.txt 6 ms 1536 KB
45.txt 6 ms 1536 KB
46.txt 84 ms 1536 KB
47.txt 1613 ms 1536 KB
48.txt 1613 ms 1536 KB
49.txt 6 ms 1536 KB
50.txt 6 ms 1536 KB
51.txt 6 ms 1536 KB
52.txt 6 ms 1536 KB
53.txt 513 ms 1536 KB
s1.txt 6 ms 1536 KB
s2.txt 6 ms 1536 KB
s3.txt 1613 ms 1536 KB
s4.txt 6 ms 1536 KB
s5.txt 6 ms 1536 KB