QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#178175 | #4306. Guess Matrix | Qingyu | TL | 3ms | 3740kb | C++20 | 3.0kb | 2023-09-13 19:02:18 | 2023-09-13 19:02:18 |
Judging History
answer
//
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
#define debug(...) fprintf (stderr, __VA_ARGS__)
#define fi first
#define se second
#define lep(i, l, r) for (int i = (l), i##_end = (r); i <= i##_end; ++ i)
#define rep(i, r, l) for (int i = (r), i##_end = (l); i >= i##_end; -- i)
char _c; bool _f; template <class T> inline void IN (T & x) {
_f = 0, x = 0; while (_c = getchar (), ! isdigit (_c)) if (_c == '-') _f = 1;
while (isdigit (_c)) x = x * 10 + _c - '0', _c = getchar (); if (_f) x = - x;
}
template <class T> inline void chkmax (T & x, T y) { if (x < y) x = y; }
template <class T> inline void chkmin (T & x, T y) { if (x > y) x = y; }
const int N = 65;
int n;
bool a[N][N];
vector <ll> sigma;
inline ll v2 (int x) { return 1ll << (ll) x; }
inline bool bit (ll x, ll b) { return (x >> b) & 1ll; }
inline void find_row () {
queue <pair <int, ll> > q;
map <pair <int, ll>, bool> ok;
q.emplace ( 0, 0 ), ok[{ 0, 0 }] = true;
while (! q.empty ()) {
auto query = [&] (int i, ll s) {
static map <pair <int, ll>, bool> failed;
lep (j, 1, i) if (failed.count ({ j, s & (v2 (j) - 1ll) })) return false ;
printf ("? 1 %d\n", i);
lep (j, 0, i - 1) putchar ('0' + bit (s, j)); puts ("");
bool x; if ( fflush (stdout), IN (x), ! x ) failed[{ i, s }] = true; return x;
};
auto extend = [&] (int i, ll s) {
if (ok.count ({ i, s }) || ! query (i, s)) return ;
while (i < n) {
if (query (i + 1, s | v2 (i))) s |= v2 (i ++ );
else if (query (i + 1, s)) ++ i;
else break ;
}
for ( ; i < n; ++ i) s = (s << 1ll) | query (i + 1, (s << 1ll) | 1ll);
sigma.emplace_back ( s );
lep (l, 0, n - 1) lep (r, l, n - 1) {
auto x = make_pair ( r - l + 1, (s >> (ll) (l)) & (v2 (r - l + 1) - 1ll) );
if (! ok.count (x)) ok[x] = true, q.push (x);
}
};
auto [i, s] = q.front (); q.pop ();
if (i == n) continue ;
extend (i + 1, s | v2 (i)), extend (i + 1, s);
}
for (auto & [x, f] : ok) if (x.fi == n) sigma.emplace_back ( x.se );
}
inline void find_column () {
int lim = sigma.size ();
vector <int> s (1, 0);
auto test = [&] (vector <int> & s) {
printf ("? %d %d\n", s.size (), n);
lep (i, 0, s.size () - 1) {
lep (j, 0, n - 1) putchar ('0' + bit (sigma[s[i]], j));
puts ("");
}
bool x; fflush (stdout), IN (x); return x;
};
while (s.size () < n) {
bool ok = false;
lep (x, 0, lim - 1) {
if ( s.emplace_back ( x ), test (s) ) { ok = true; break ; }
s.pop_back ();
}
if (! ok) break ;
}
while (s.size () < n) {
lep (x, 0, lim - 1) {
vector <int> t (1, x);
for (auto & y : s) t.emplace_back ( y );
if ( test (t) ) { swap (s, t); break ; }
}
}
lep (i, 0, n - 1) lep (j, 0, n - 1) a[i][j] = bit (sigma[s[i]], j);
}
signed main () {
IN (n), find_row (), find_column ();
puts ("!");
lep (i, 0, n - 1) { lep (j, 0, n - 1) putchar (a[i][j] + '0'); puts (""); }
return fflush (stdout), 0;
}
Details
Test #1:
score: 100
Accepted
time: 0ms
memory: 3644kb
Test #2:
score: 0
Accepted
time: 0ms
memory: 3664kb
Test #3:
score: 0
Accepted
time: 0ms
memory: 3656kb
Test #4:
score: 0
Accepted
time: 1ms
memory: 3660kb
Test #5:
score: 0
Accepted
time: 1ms
memory: 3740kb
Test #6:
score: 0
Accepted
time: 1ms
memory: 3724kb
Test #7:
score: 0
Accepted
time: 1ms
memory: 3660kb
Test #8:
score: 0
Accepted
time: 0ms
memory: 3700kb
Test #9:
score: 0
Accepted
time: 1ms
memory: 3648kb
Test #10:
score: 0
Accepted
time: 3ms
memory: 3728kb
Test #11:
score: 0
Accepted
time: 0ms
memory: 3700kb
Test #12:
score: -100
Time Limit Exceeded