Skip to content

Instantly share code, notes, and snippets.

@iambrj
Created March 14, 2022 10:50
Show Gist options
  • Save iambrj/e4123aa6122996dc7b158e371638e732 to your computer and use it in GitHub Desktop.
Save iambrj/e4123aa6122996dc7b158e371638e732 to your computer and use it in GitHub Desktop.
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e6 + 5;
int n, S_cnt[NMAX];
unordered_map<string, vector<int>> payoff;
vector<string> psne;
vector<string> gen(int i) {
vector<string> v;
if(i == 0) {
for(int s = 1; s <= S_cnt[i]; s++)
v.push_back(to_string(s));
} else {
vector<string> prev = gen(i - 1);
for(int s = 1; s <= S_cnt[i]; s++) {
for(auto p : prev) {
v.push_back(p + to_string(s));
}
}
}
return v;
}
void solve() {
cin >> n;
for(int i = 0; i < n; i++) {
cin >> S_cnt[i];
}
vector<string> S = gen(n - 1);
vector<int> tmp(n);
for(auto s : S) {
for(int i = 0; i < n; i++) {
cin >> tmp[i];
}
payoff[s] = tmp;
}
for(auto s : S) {
bool ok = true;
for(int i = 0; i < n && ok; i++) {
for(int sj = 1; sj <= S_cnt[i] && ok; sj++) {
string other_s = s;
other_s[i] = 48 + sj;
if(payoff[s][i] < payoff[other_s][i]) {
ok = false;
}
}
}
if(ok) {
psne.push_back(s);
}
}
cout << psne.size() << endl;
for(auto p : psne) {
for(auto i : p) {
cout << i << " ";
}
cout << endl;
}
}
int main() {
std::ios_base::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment