Submission #14931857


Source Code Expand

Copy
#include<bits/stdc++.h>
#define rep(i, x) for (ll i = 0; i < (x); i++)
#define chmax(x, a)  do { x = max(x, a); } while(0)

using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

ull N, A, B, X, S;

const ll M = 50;
ll dp[M][2][2];

int main(void) {
  cin >> N >> A >> B;
  rep(i, N-2) {
    ull x;
    cin >> x;
    X ^= x;
  }
  S = A + B;

  // 初期化
  rep(i, M) rep(j, 2) rep(k, 2) dp[i][j][k] = -1;
  rep(a, 2) {
    ull b = a ^ (X & 1);
    ull carry = a & b;
    ull _sum = a ^ b;
    if (_sum != (S & 1)) continue;
    ull over = a > (A & 1);
    chmax(dp[0][carry][over], a);
  }

  // 配るDP
  rep(i, M-1) rep(j, 2) rep(k, 2) rep(a, 2) {
    if (dp[i][j][k] == -1) continue;
    ull ni = i + 1;
    ull b = a ^ ((X >> ni) & 1);
    ull _sum = (a + b + j) & 1;
    ull _carry = ((a + b + j) & 2) > 0;
    if (_sum != ((S >> ni) & 1)) continue;
    ull over;
    if (a >  ((A >> ni) & 1)) over = 1;
    if (a <  ((A >> ni) & 1)) over = 0;
    if (a == ((A >> ni) & 1)) over = k;
    chmax(dp[i+1][_carry][over], dp[i][j][k] | (a << ni));
  }

  ll a = dp[M-1][0][0];
  if (a == -1 || a == 0) {
    cout << -1 << endl;
    return 0;
  }
  cout << (A-a) << endl;

  return 0;
}

Submission Info

Submission Time
Task F - Unfair Nim
User bobuhiro11
Language C++ (GCC 9.2.1)
Score 600
Code Size 1276 Byte
Status
Exec Time 8 ms
Memory 3608 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:2:36: warning: comparison of integer expressions of different signedness: ‘ll’ {aka ‘long long int’} and ‘ull’ {aka ‘long long unsigned int’} [-Wsign-compare]
    2 | #define rep(i, x) for (ll i = 0; i < (x); i++)
      |                                    ^
./Main.cpp:16:3: note: in expansion of macro ‘rep’
   16 |   rep(i, N-2) {
      |   ^~~
./Main.cpp:30:18: warning: comparison of integer expressions of different signedness: ‘ll’ {aka ‘long long int’} and ‘ull’ {aka ‘long long unsigned int’} [-Wsign-compare]
   30 |     ull over = a > (A & 1);
      |                ~~^~~~~~~~~
./Main.cpp:43:11: warning: comparison of integer expressions of different signedness: ‘ll’ {aka ‘long long int’} and ‘ull’ {aka ‘long long unsigned int’} [-Wsign-compare]
   43 |     if (a >  ((A >> ni) & 1)) over = 1;
      |         ~~^~~~~~~~~~~~~~~~~~
./Main.cpp:44:11: warning: comparison of integer expressions of different signedness: ‘ll’ {aka ‘long long int’} and ‘ull’ {aka ‘long long unsigned int’} [-Wsign-compare]
   44 |     if (a <  ((A >> ni) & 1)) over = 0;
      |         ~~^~~~~~~~~~~~~~~~~~
./Main.cpp:45:11: warning: comparison of integer expressions of different signedness: ‘ll’ {aka ‘long long int’} and ‘ull’ {aka ‘long long unsigned int’} [-Wsign-compare]
   45 |     if (a == ((A >> ni) & 1)) over = k;
      |         ~~^~~~~~~~~~~~~~~~~~

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt
All 600 / 600 hand_01.txt, hand_02.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt, n2_01.txt, n2_02.txt, n2_03.txt, n2_04.txt, n3_01.txt, n3_02.txt, n3_03.txt, n3_04.txt
after_contest 0 / 0 after_contest_01.txt
Case Name Status Exec Time Memory
after_contest_01.txt 8 ms 3524 KB
hand_01.txt 2 ms 3380 KB
hand_02.txt 2 ms 3540 KB
n2_01.txt 2 ms 3544 KB
n2_02.txt 2 ms 3540 KB
n2_03.txt 3 ms 3532 KB
n2_04.txt 1 ms 3404 KB
n3_01.txt 2 ms 3540 KB
n3_02.txt 3 ms 3540 KB
n3_03.txt 3 ms 3416 KB
n3_04.txt 3 ms 3608 KB
random_01.txt 2 ms 3500 KB
random_02.txt 2 ms 3564 KB
random_03.txt 2 ms 3384 KB
random_04.txt 2 ms 3348 KB
random_05.txt 2 ms 3416 KB
random_06.txt 2 ms 3412 KB
random_07.txt 2 ms 3604 KB
random_08.txt 2 ms 3532 KB
sample_01.txt 2 ms 3540 KB
sample_02.txt 3 ms 3604 KB
sample_03.txt 2 ms 3404 KB
sample_04.txt 2 ms 3564 KB
sample_05.txt 2 ms 3536 KB