D
D
dalbio2020-07-25 14:36:54
C++ / C#
dalbio, 2020-07-25 14:36:54

Why am I getting the wrong answer?

There is a task: https://codeforces.com/contest/1383/problem/B
I pass the tests from the example, I get WA by 3.
The code itself:

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
bool cmp(const int& a, const int& b) {
  return a > b;
}
int main() {
  IOS;
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    int mx = 0;
    vector<bitset<30>>game(2);
    int tek = 0;
    game[0] = 0;// coa
    game[1] = 0;// friend
    vector<int>a(30);
    vector<pair<int,int>>nused;
    vector<int>used;
    for (int i = 0; i < n; i++) {
      int x;
      cin >> x;
      if (x != 0) {
        int pos = log(x) / log(2);
        if (a[pos] < 2) {
          a[pos]++;
          used.push_back(x);
          //game[tek] = game[tek] ^ bx;
        }
        else nused.push_back({ pos,x });
      }
    }
    sort(used.begin(), used.end(), cmp);
    for (int i = 0; i < used.size(); i++) {
      bitset<30>bx = used[i];
      game[tek] = game[tek] ^ bx;
      tek = 1 - tek;
    }
    sort(nused.begin(), nused.end());
    for (int i = 0; i < nused.size(); i++) {
      bitset<30>cur = nused[i].second;
      game[tek] = game[tek] ^ cur;
      tek = 1 - tek;
    }
    if (game[0].to_ullong() > game[1].to_ullong()) cout << "WIN";
    if (game[0].to_ullong() < game[1].to_ullong()) cout << "LOSE";
    if (game[0].to_ullong() == game[1].to_ullong()) cout << "DRAW";
    cout << "\n";
  }
}

Solution idea: Initially, I use pos to find the number of the maximum bit (1s) (for 001 it's 0 for 010 it's 1, etc.). And I add them to those used so that the mask game[0] and game[1] get the bits in the maximum position (and not only).
As soon as I have more than 2 numbers with 1 in some maximum bit (meaning that these numbers have the same maximum bit number) I add them to nused (because 1^1=0). Then I sort nused like this how it is profitable for everyone to spoil bits with a lower value, i.e. it is more profitable to spoil the bit that gives 4 than the bit that gives 8.
Then I just compare the numbers

Answer the question

In order to leave comments, you need to log in

1 answer(s)
W
Wataru, 2020-07-25
@dalbio

You say you're trying to take numbers to "spoil" the smaller bits, but that might not be the case.
If you have numbers 4,4,4,4,5,6,1,1, then it is advantageous to take exactly 6, because it will make the second bit one, which cannot be done by taking 5.
You have the wrong solution to the problem.
The correct solution is: Find the most significant bit that has an odd number of ones in the array a.
If there are none, then the answer is Draw. Because if there is an even number of units in some category, and the first player gets x of them, then the second player gets 2k-x, which will have the same parity as x. This means that in this category the final values ​​cannot differ at all. Do not distribute as numbers, even if the players can make a different number of moves.
Now we know that in this discharge there will definitely be a difference. Because it is impossible to distribute an odd number of units into 2 groups with the same parity. Victory is determined only by this category, because it is the oldest of the distinctions. Now we have 2k+1 numbers with 1s in this digit and n-2k-1 numbers with 0s in this digit. There is no need to look further at the bits - whoever takes an odd number of numbers from 2 * k + 1 - he won.
Those. you then need to solve a very simple problem: Given a pair of numbers (i, j), i is odd, there are i necessary objects and j unnecessary ones, players take objects in turn. Whoever takes an odd number of necessary objects - he won.
Here, to derive a solution, you can write dynamic programming, which for a pair (i, j) will say whether the player can take an even / odd number of the necessary numbers, if there are i, and there are still j unnecessary ones. When calculating, iterate over the options, which type of objects is taken and see if your opponent can spoil the parity for you on a smaller problem.
Next, you need to look at the pattern on small numbers and draw up a solution, because all this dynamics will not work for you in time for these restrictions.
I'm too lazy to solve the problem further, but it seems that with i=1 the answer is WIN, with i>0 - the answer is Win, if i+j=n is even. Otherwise - Lose.

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question