Submission #2289041


Source Code Expand

Copy
#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

set< int64 > g[51];
int N, A[50], B[50];

int64 po[51];

void rec(int base, int cur_val, int64 dame, int64 bit) {
  if(B[base] == cur_val) {
    g[base].emplace(bit);
    return;
  }
  for(int64 i = cur_val; i >= 1; i--) {
    if(i <= 17 && !((dame >> i) & 1)) {

    } else if(i <= 17) {
      rec(base, cur_val % i, dame, bit);
    } else {
      rec(base, cur_val % i, dame, bit | (1LL << i));
    }
  }
}

bool check(int64 bitmask) {
  for(int i = 0; i < N; i++) {
    bool f = false;

    for(auto &x : g[i]) {
      if((bitmask & x) == x) {
        f = true;
        break;
      }
    }
    if(!f) return false;
  }
  return true;
}

int64 rec2(int64 bitmask, int64 last = 18) {
  if(check(bitmask)) return 0;
  if(last > 51) return (1LL << 61);
  int64 ret = rec2(bitmask, last + 1);

  int64 mask2 = (1LL << 61) - 1;
  for(int i = 0; i < last; i++) mask2 ^= 1LL << i;
  mask2 = mask2 | bitmask;

  bool check = false;
  for(int i = 0; i < N; i++) {
    for(auto &x : g[i]) {
      if((mask2 & x) == x) {
        if((x >> last) & 1) {
          check = true;
        }
      }
    }
  }
  if(check) {
    ret = min(ret, rec2(bitmask | (1LL << last), last + 1) + po[last]);
  }
  return ret;
}

int main() {

  po[0] = 1;
  for(int i = 1; i < 51; i++) {
    po[i] = po[i - 1] * 2;
  }

  cin >> N;
  for(int i = 0; i < N; i++) {
    cin >> A[i];
  }
  for(int i = 0; i < N; i++) {
    cin >> B[i];
  }
  int64 ret = (1LL << 61);

  for(int i = 0; i < (1 << 18); i++) {
    if(i & 1) continue;

    int64 sum = 0;
    for(int j = 0; j < 18; j++) {
      if((i >> j) & 1) {
        sum += po[j];
      }
    }


    for(int k = 0; k < N; k++) {
      g[k].clear();
      rec(k, A[k], i, 0);
    }
    ret = min(ret, sum + rec2(0));
  }
  if(ret >= (1LL << 61)) cout << -1 << endl;
  else cout << ret << endl;
}

Submission Info

Submission Time
Task C - Remainder Game
User ei13333
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1993 Byte
Status
Exec Time 2103 ms
Memory 256 KB

Judge Result

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 2103 ms 256 KB
02.txt 2103 ms 256 KB
03.txt 2103 ms 256 KB
04.txt 1315 ms 256 KB
05.txt 2103 ms 256 KB
06.txt 2103 ms 256 KB
07.txt 2103 ms 256 KB
08.txt 2103 ms 256 KB
09.txt 2103 ms 256 KB
10.txt 2103 ms 256 KB
11.txt 2103 ms 256 KB
12.txt 159 ms 256 KB
13.txt 315 ms 256 KB
14.txt 2103 ms 256 KB
15.txt 2103 ms 256 KB
16.txt 2103 ms 256 KB
17.txt 2103 ms 256 KB
18.txt 2103 ms 256 KB
19.txt 2103 ms 256 KB
20.txt 2103 ms 256 KB
21.txt 2103 ms 256 KB
22.txt 2103 ms 256 KB
23.txt 2103 ms 256 KB
24.txt 2103 ms 256 KB
25.txt 2103 ms 256 KB
26.txt 2103 ms 256 KB
27.txt 2103 ms 256 KB
28.txt 2103 ms 256 KB
29.txt 2103 ms 256 KB
30.txt 2103 ms 256 KB
31.txt 2103 ms 256 KB
32.txt 1899 ms 256 KB
33.txt 2103 ms 256 KB
34.txt 2103 ms 256 KB
35.txt 2103 ms 256 KB
36.txt 2103 ms 256 KB
37.txt 2103 ms 256 KB
38.txt 2103 ms 256 KB
39.txt 2103 ms 256 KB
40.txt 2103 ms 256 KB
41.txt 2103 ms 256 KB
42.txt 2103 ms 256 KB
43.txt 2103 ms 256 KB
44.txt 2103 ms 256 KB
45.txt 2103 ms 256 KB
46.txt 2103 ms 256 KB
47.txt 2103 ms 256 KB
48.txt 2103 ms 256 KB
49.txt 1910 ms 256 KB
50.txt 2103 ms 256 KB
51.txt 1775 ms 256 KB
52.txt 1405 ms 256 KB
53.txt 2103 ms 256 KB
s1.txt 778 ms 256 KB
s2.txt 393 ms 256 KB
s3.txt 245 ms 256 KB
s4.txt 36 ms 256 KB
s5.txt 1788 ms 256 KB