QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#178175#4306. Guess MatrixQingyuTL 3ms3740kbC++203.0kb2023-09-13 19:02:182023-09-13 19:02:18

Judging History

你现在查看的是最新测评结果

  • [2023-09-13 19:02:18]
  • 评测
  • 测评结果:TL
  • 用时:3ms
  • 内存:3740kb
  • [2023-09-13 19:02:18]
  • 提交

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

详细

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