QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #265680 | #7740. Puzzle: Question Mark | ucup-team1191# | WA | 244ms | 3900kb | C++20 | 12.7kb | 2023-11-25 20:19:19 | 2023-11-25 20:19:19 |
Judging History
answer
/*
author: Maksim1744
created: 25.11.2023 14:18:46
*/
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ld = long double;
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define sum(a) ( accumulate ((a).begin(), (a).end(), 0ll))
#define mine(a) (*min_element((a).begin(), (a).end()))
#define maxe(a) (*max_element((a).begin(), (a).end()))
#define mini(a) ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a) ( max_element((a).begin(), (a).end()) - (a).begin())
#define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())
template<typename T> vector<T>& operator-- (vector<T> &v){for (auto& i : v) --i; return v;}
template<typename T> vector<T>& operator++ (vector<T> &v){for (auto& i : v) ++i; return v;}
template<typename T> istream& operator>>(istream& is, vector<T> &v){for (auto& i : v) is >> i; return is;}
template<typename T> ostream& operator<<(ostream& os, vector<T> v){for (auto& i : v) os << i << ' '; return os;}
template<typename T, typename U> pair<T,U>& operator-- (pair<T, U> &p){--p.first; --p.second; return p;}
template<typename T, typename U> pair<T,U>& operator++ (pair<T, U> &p){++p.first; ++p.second; return p;}
template<typename T, typename U> istream& operator>>(istream& is, pair<T, U> &p){is >> p.first >> p.second; return is;}
template<typename T, typename U> ostream& operator<<(ostream& os, pair<T, U> p){os << p.first << ' ' << p.second; return os;}
template<typename T, typename U> pair<T,U> operator-(pair<T,U> a, pair<T,U> b){return mp(a.first-b.first, a.second-b.second);}
template<typename T, typename U> pair<T,U> operator+(pair<T,U> a, pair<T,U> b){return mp(a.first+b.first, a.second+b.second);}
template<typename T, typename U> void umin(T& a, U b){if (a > b) a = b;}
template<typename T, typename U> void umax(T& a, U b){if (a < b) a = b;}
#ifdef HOME
#define SHOW_COLORS
#include "/mnt/c/Libs/tools/print.cpp"
#else
#define show(...) void(0)
#define debugf(fun) fun
#define debugv(var) var
#define mclock void(0)
#define shows void(0)
#define debug if (false)
#define OSTREAM(...) ;
#define OSTREAM0(...) ;
#endif
template<class Fun>
class y_combinator_result {
Fun fun_;
public:
template<class T>
explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
template<class ...Args>
decltype(auto) operator()(Args &&...args) {
return fun_(std::ref(*this), std::forward<Args>(args)...);
}
};
template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}
// auto gcd = std::y_combinator([](auto gcd, int a, int b) -> int {
// return b == 0 ? a : gcd(b, a % b);
// });
template<size_t N>
bool operator < (const bitset<N>& a, const bitset<N>& b) {
if (a == b) return false;
int ind = (a ^ b)._Find_first();
return b.test(ind);
}
struct Cmp {
template<size_t N>
bool operator () (const bitset<N>& a, const bitset<N>& b) const {
if (a == b) return false;
int ind = (a ^ b)._Find_first();
return b.test(ind);
}
};
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
vector<vector<string>> preps = {
vector<string>{
".AA",
"BAB",
"BBA",
},
vector<string>{
"..AA.",
"BBACC",
".BCAC",
"BDDEE",
".DEDE",
},
vector<string>{
".A.ABB.",
"CCAABDD",
"CECEDBD",
".EEFFGG",
"HH.FGFG",
"HIIJJKK",
"IHIJKJK",
},
vector<string>{
".AABBCCDD",
"EEABCBCDF",
"EAGGHHIFD",
"JEJGHIHFF",
"JJGKKIILL",
"MMKNKNOLO",
"MPQQNNOOL",
"PMQRRSSTT",
"PPRQRSTST",
},
vector<string>{
"ABACCDEEFFGGH",
"BAACDCEFEFGHG",
"BBIIDDJJKKLHH",
"MIMINJNJKLKOO",
"MMPQPNNRRLLOS",
"TTQPPUURVRVSO",
"TWQQXXUYYVVSS",
"WTZZXU[Y[//]]",
"WWZ^^X[[Y/]/]",
"__^Z^``aabbcc",
"_dee.`a`abcbc",
"d_effgghhiijj",
"ddfefghghijij",
},
vector<string>{
"ABAB",
"AABB",
},
vector<string>{
"AA",
"AB",
"BA",
"BB",
},
};
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int last = 0;
vector<vector<int>> v(n, vector<int>(n, 0));
auto fill_at = [&](int i, int j, int n, int m) {
assert(i + n <= v.size());
assert(j + m <= v.size());
for (const auto& prep : preps) {
if (prep.size() == n && prep[0].size() == m) {
map<char, int> who;
for (int x = 0; x < n; ++x) {
for (int y = 0; y < m; ++y) {
if (prep[x][y] == '.') continue;
if (!who.count(prep[x][y])) {
++last;
who[prep[x][y]] = last;
}
assert(v[x + i][y + j] == 0);
v[x + i][y + j] = who[prep[x][y]];
}
}
return;
}
}
assert(false);
};
auto fill88 = [&](int i, int j) {
for (int x = 0; x < 8; x += 2)
for (int y = 0; y < 8; y += 4)
fill_at(i+x, y+j, 2, 4);
};
if (n % 2 == 0) {
if (n % 4 == 0) {
for (int i = 0; i < n; i += 2) {
for (int j = 0; j < n; j += 4) {
fill_at(i, j, 2, 4);
}
}
} else {
for (int i = 0; i < n; i += 2) {
for (int j = 0; j + 4 <= n; j += 4) {
fill_at(i, j, 2, 4);
}
}
for (int i = 0; i + 4 <= n; i += 4) {
fill_at(i, n - 2, 4, 2);
}
}
} else {
if (n == 1) {
} else if (n == 3 || n == 5 || n == 7) {
fill_at(0, 0, n, n);
} else {
auto start_from = (n % 8 < 4 ? 9 : 13);
int k = start_from;
fill_at(0, 0, k, k);
while (k + 8 <= n) {
fill_at(k-1, k-1, 9, 9);
for (int i = 0; i + 8 <= k; i += 8) {
fill88(k, i);
fill88(i, k);
}
k += 8;
}
if (k != n) {
fill_at(k-1, k-1, 3, 3);
for (int i = 0; i + 4 <= k; i += 4) {
fill_at(i, k, 4, 2);
fill_at(k, i, 2, 4);
}
}
}
}
cout << last << '\n';
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cout << v[i][j] << " \n"[j + 1 == n];
}
}
#ifdef HOUSE
cout.flush();
#endif
}
// const int n = 7;
// const int m = 7;
// static_assert(n >= 4);
// static_assert(m >= 4);
// using B = bitset<n * m>;
// auto ind = [&](int i, int j) {
// return i * m + j;
// };
// vector<B> base;
// {
// B square = 0;
// square.set(ind(1, 1));
// square.set(ind(1, 2));
// square.set(ind(2, 1));
// square.set(ind(2, 2));
// {
// auto u = square;
// u.flip(ind(1, 1));
// u.flip(ind(0, 1));
// base.pb(u);
// }
// {
// auto u = square;
// u.flip(ind(1, 1));
// u.flip(ind(1, 0));
// base.pb(u);
// }
// {
// auto u = square;
// u.flip(ind(1, 2));
// u.flip(ind(1, 3));
// base.pb(u);
// }
// {
// auto u = square;
// u.flip(ind(1, 2));
// u.flip(ind(0, 2));
// base.pb(u);
// }
// {
// auto u = square;
// u.flip(ind(2, 1));
// u.flip(ind(2, 0));
// base.pb(u);
// }
// {
// auto u = square;
// u.flip(ind(2, 1));
// u.flip(ind(3, 1));
// base.pb(u);
// }
// {
// auto u = square;
// u.flip(ind(2, 2));
// u.flip(ind(2, 3));
// base.pb(u);
// }
// {
// auto u = square;
// u.flip(ind(2, 2));
// u.flip(ind(3, 2));
// base.pb(u);
// }
// }
// for (auto& x : base) {
// while ((x >> m).count() == 4) x >>= m;
// while (true) {
// bool ok = true;
// for (int i = 0; i < n; ++i) {
// if (x[ind(i, 0)]) {
// ok = false;
// break;
// }
// }
// if (ok) x >>= 1;
// else break;
// }
// }
// // auto print = [&](const B& b) {
// // for (int i = 0; i < n; ++i) {
// // for (int j = 0; j < n; ++j) {
// // cout << ".#"[b[ind(i, j)]];
// // }
// // cout << '\n';
// // }
// // cout << endl;
// // };
// sort(base.begin(), base.end());
// base.erase(unique(base.begin(), base.end()), base.end());
// vector<B> v;
// for (auto b : base) {
// while (true) {
// v.pb(b);
// if ((b << m).count() != 4) break;
// b <<= m;
// }
// }
// swap(v, base);
// v.clear();
// for (auto b : base) {
// while (true) {
// v.pb(b);
// bool ok = true;
// for (int i = 0; i < n; ++i) {
// if (b.test(ind(i, m-1))) {
// ok = false;
// break;
// }
// }
// if (!ok) break;
// b <<= 1;
// }
// }
// swap(v, base);
// sort(base.begin(), base.end());
// // for (auto& x : base)
// // print(x);
// int best = 0;
// map<B, B, Cmp> par;
// vector<B> suf = base;
// for (int i = (int)suf.size() - 2; i >= 0; --i)
// suf[i] |= suf[i + 1];
// best = 0;
// y_combinator([&](auto dfs, B mask, int i) -> void {
// // if (mask.test(0)) return;
// if (mask.count() > best) {
// best = mask.count();
// cout << "new best: " << best << ", empty: " << mask.size() - mask.count() << endl;
// auto ms = mask;
// char c = 'A';
// vector<string> field(n, string(m, '.'));
// while (ms.count()) {
// auto here = ms ^ par[ms];
// for (int i = 0; i < n; ++i) {
// for (int j = 0; j < m; ++j) {
// if (here.test(ind(i, j))) {
// field[i][j] = c;
// }
// }
// }
// ++c;
// ms ^= here;
// }
// for (auto s : field) {
// cout << s << endl;
// }
// }
// if (i == base.size()) return;
// if ((mask | suf[i]).count() <= best) return;
// B other = 0;
// for (int j = i; j < base.size(); ++j)
// if ((mask & base[j]).count() == 0)
// other |= base[j];
// if ((mask | other).count() <= best) return;
// if ((mask & base[i]).count() == 0 && !par.count(mask | base[i])) {
// par[mask | base[i]] = mask;
// dfs(mask | base[i], i + 1);
// }
// dfs(mask, i + 1);
// })(B{0}, 0);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3584kb
input:
2 3 4
output:
2 0 1 1 2 1 2 2 2 1 4 1 2 1 2 1 1 2 2 3 4 3 4 3 3 4 4
result:
ok Correct. (2 test cases)
Test #2:
score: -100
Wrong Answer
time: 244ms
memory: 3900kb
input:
246 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...
output:
0 0 0 0 0 0 0 2 0 1 1 2 1 2 2 2 1 4 1 2 1 2 1 1 2 2 3 4 3 4 3 3 4 4 5 0 0 1 1 0 2 2 1 3 3 0 2 3 1 3 2 4 4 5 5 0 4 5 4 5 8 1 2 1 2 7 7 1 1 2 2 7 8 3 4 3 4 8 7 3 3 4 4 8 8 5 6 5 6 0 0 5 5 6 6 0 0 11 0 1 0 1 2 2 0 3 3 1 1 2 4 4 3 5 3 5 4 2 4 0 5 5 6 6 7 7 8 8 0 6 7 6 7 8 9 9 10 10 11 11 9 8 9 10 11 10 ...
result:
wrong answer Jury has better answer. Participant 94, jury 110 (test case 21)