Почему я получаю неверный ответ?

Question

[dalbio]

Имеется задача: https://codeforces.com/contest/1383/problem/B
Тесты из примера прохожу,получаю WA на 3.
Сам код:

#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";
	}
}

Идея решения: Изначально я нахожу с помощью pos номер максимального бита (1-цы) (для 001 это 0 для 010 это 1 и т.д ). И добавляю их в использующиеся,чтобы маска game[0] и game[1] получили биты в максимальной позиции (и не только).
Как только у меня имеется более 2-х чисел с 1 в каком-то максимальном бите (имеется ввиду,что у этих чисел номер максимального бита равен) я добавляю их в nused (так как 1^1=0).Затем сортирую nused так как каждому выгодно портить биты с меньшим значением ну т.е выгоднее испортить бит который даёт 4,чем бит который даёт 8.
Затем я просто сравниваю числа

Comments

[Wataru]

dalbio, Опишите ваше решение. Без этого сложно найти ошибку в коде.

[dalbio]

wataru, Описал (если что-то непонятно пишите)

Answer 1

[Wataru]

Вы говорите, что пытаетесь брать числа, чтобы "портить" меньшие биты, но ведь это может быть не так.
Если у вас числа 4,4,4,4,5,6,1,1 - то выгодно брать именно 6, потому что оно сделает второй бит единицей, что никак невозможно сделать, взяв 5.
У вас неправильное решение задачи.

Правильное решение такое: Найдите самый старший бит, в котором нечетное количество единиц в массиве a.

Если таких нет - то ответ Draw. Потому что, если в каком-то разряде единиц четное количество, и x из них достанется первому игроку, то второму достанется 2k-x, что будет иметь ту же четность, что и x. А значит в этом разряде итоговые значения отличаться не могут вообще. Как числа не распределяй, даже если игроки могут делать разное количество ходов.

Теперь мы знаем, что в этом разряде различие точно будет. Потому что нельзя нечетное количество единиц распределить на 2 группы с одинаковой четностью. Победа определяется только этим разрядом, ведь он самый старший из различий. Теперь у нас есть 2k+1 чисел c 1 в этом разряде и n-2k-1 чисел с 0 в этом разряде. На биты дальше смотреть не надо - кто возьмет нечетное количество чисел из 2*k+1 - тот победил.

Т.е. вам дальше надо решить совсем простую задачу: Дана пара чисел (i,j), i - нечетно, есть i нужных объектов и j ненужных, игроки по-очереди берут объекты. Кто возьмет нечетное количество нужных объектов - тот и победил.

Тут для вывода решения можно написать динамическое программирование, которое для пары (i,j) - будет говорить, сможет ли игрок взять четное/нечетное количество нужных чисел, если их i, и еще есть j ненужных. При расчете перебирайте варианты, какой из типов объектов берется и смотрите, а сможет ли оппонент вам четность испортить на меньшей задаче.

Дальше надо посмотреть на паттерн на маленьких числах и составить решение, потому что вся эта динамика у вас по времени не зайдет для данных ограничений.

Мне лень решать дальше задачу, но похоже, что при i=1 ответ - WIN, при i>0 - ответ Win, если i+j=n - четно. Иначе - Lose.

Comments

[dalbio]

"выгодно брать именно 6" у 6 макс бит (его позиция это 3) (само число 110) портит 2 и 1-й бит 5-ка портит 2-й и 0-й бит (101). (мб я что-то не так понял)?

[Wataru]

dalbio, Я вам расписал правильное, логически обоснованное решение. Оно вообще не такое, как ваше и ему противоречит.
Старший ненулевой разряд может вообще значения не имеет, если там четное количество единиц. Я могу вам составить тест, когда будет выгодно брать 5 вместо 6, или 6 вместо 5 - все зависит от остальных чисел в массиве.

[dalbio]

А сам список выглядит как 001,001,100,100,100,100,101,110 сначала идут меньшие биты,а если у чисел равны макс.биты то сначала идут те что имеют более меньшие биты.

[Wataru]

dalbio, еще раз, прочитайте мой ответ целиком, пожалуйста. Если в старшем разряде четное количество единиц в массиве, то в этом разряде результаты двух игроков различаться НЕ МОГУТ. Вообще, никак! Вы хоть все числа в массиве одному отдайте, хоть только одно, хоть левую половину, хоть каждое четное. Математически в этом разряде числа у двух игроков будут равны.

Ну как пример, если у вас таких 2 числа имеют старший разряд, то или оба пойдут к первому игроку и результат xor будет 0 и там и там, или по одному числу каждому игроку и результат xor будет 1 и там и там, или оба числа отойдут второму игроку, что также даст нули везде.

Ваше решение смотрит и что-то решает ориентируясь на самый старший ненулевой разряд. Все, оно уже неправильное. Дальше в логику можно не вникать.