Submission #1260879

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260879		new_acc	Council (JOI23_council)	C++20	25 / 100	155 ms	2404 KiB

council

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;

#define st first
#define nd second
#define f(a, c, b) for (int a = c; b > a; a++)
#define pb push_back
#define all(a) a.begin(), a.end()
#define wczytaj(a, c, n) a.resize(n); f(i, c, n) cin >> a[i];
#define sz(a) int(a.size())
#define wypisz(a, c) f(i, c, sz(a)) cout << a[i] << " "; cout << "\n";

const int DUZO = 10000000;

int n;
int m;

vector<int> parlament;
vector<int> czy_podmaska;
vector<pair<int, int>> najb_podmaska; //trzymamy najblizsza i druga najblizsza bo jesli aktualny marszalek bedzie ta maska not to kupa
vector<int> ile_glosuje;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	int p1;
	parlament.resize(n, 0);
	ile_glosuje.resize(m, 0);
	czy_podmaska.resize((1 << m));
	f(i, 0, n) {
		f(j, 0, m) {
			cin >> p1;
			if (p1) {parlament[i] += (1 << j); ile_glosuje[j]++;};
		}
		czy_podmaska[parlament[i]]++;
	}
	//obliczam czy istnieja podmaski innych masek 
	f(j, 0, m) {
		f(i, 1, (1 << m)) {
			if (i & (1 << j)) {
				czy_podmaska[i] += czy_podmaska[i - (1 << j)];
			}
		}
	}
	
	najb_podmaska.resize(1 << m, {DUZO, DUZO});
	
	for (int posel: parlament) {
		if (najb_podmaska[posel].st == DUZO) najb_podmaska[posel].st = 0;
		else najb_podmaska[posel].nd = 0;
	}
	
	/*for (pair<int, int> ele: najb_podmaska) {
		cout << ele.st << " " << ele.nd << "\n";
	}
	cout << "\n\n";*/
	
	vector<int> p2;
	f(j, 0, m) {
		f(i, 0, (1 << m) - 1) {
			if (!(i & (1 << j))) {
				p2 = {najb_podmaska[i].st, najb_podmaska[i].nd, najb_podmaska[i ^ (1 << j)].st + 1, najb_podmaska[i ^ (1 << j)].nd + 1};
				sort(all(p2));
				najb_podmaska[i] = {p2[0], p2[1]};
			} else {
				p2 = {najb_podmaska[i].st, najb_podmaska[i].nd, najb_podmaska[i ^ (1 << j)].st, najb_podmaska[i ^ (1 << j)].nd};
				sort(all(p2));
				najb_podmaska[i] = {p2[0], p2[1]};
			}
		}
	}
	
	/*for (pair<int, int> ele: najb_podmaska) {
		cout << ele.st << " " << ele.nd << "\n";
	}
	cout << "\n\n";*/
	
	int aktl_maska;
	int wyglosuj = (n/2);
	int ile_pot;
	
	int p5;
	
	f(i, 0, n) {
		f(j, 0, m) {
			if (parlament[i] & (1 << j)) ile_glosuje[j]--;
		}
		aktl_maska = 0;
		ile_pot = 0;
		f(j, 0, m) {
			if (ile_glosuje[j] - 1 >= wyglosuj) {
				ile_pot++;
				aktl_maska += (1 << j);
			} else if (ile_glosuje[j] < wyglosuj) {
				aktl_maska += (1 << j);
			} else {
				ile_pot++;
			}
		}
		if ((parlament[i] & aktl_maska) == parlament[i]) {
			if (czy_podmaska[aktl_maska] >= 2) {
				cout << ile_pot << "\n";
			} else {
				cout << ile_pot - najb_podmaska[aktl_maska].nd << "\n";
			}
		} else {
			if (czy_podmaska[aktl_maska]) {
				cout << ile_pot << "\n";
			} else {
				p5 = 0; //na ilu bitach parlament przeszkadza temu drugiemu
				f(j, 0, m) {
					if ((parlament[i] & (1 << j)) && (!(aktl_maska & (1 << j)))){
						p5++;
					}
				}
				if (najb_podmaska[aktl_maska].st == p5) {
					cout << ile_pot - najb_podmaska[aktl_maska].nd << "\n";
				} else {
					cout << ile_pot - najb_podmaska[aktl_maska].st << "\n";
				}
			}
		}
		f(j, 0, m) {
			if (parlament[i] & (1 << j)) ile_glosuje[j]++;
		}
	}
	
	return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 8
• Subtask 3: 6 / 6
• Subtask 4: 19 / 19
• Subtask 5: 0 / 15
• Subtask 6: 0 / 22
• Subtask 7: 0 / 22