QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#178174#4306. Guess MatrixQingyuAC ✓160ms13408kbC++201.8kb2023-09-13 18:58:552023-09-13 18:58:55

Judging History

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

  • [2023-09-13 18:58:55]
  • 评测
  • 测评结果:AC
  • 用时:160ms
  • 内存:13408kb
  • [2023-09-13 18:58:55]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define pii std::pair<int,ll>
#define sc second
#define fr first
int n;
std::set<pii> f;
inline bool qry(pii u){
	int y=u.first;ll x=u.second;
	for(int i=1;i<=y;i++)
		if(f.count({i,x&((1ll<<i)-1)}))
			return 0;
	printf("? 1 %d\n",y);
	for(int i=y-1;~i;i--)
		putchar('0'+((x>>i)&1));
	puts("");
	fflush(stdout);
	static int res;
	scanf("%d",&res);
	if(!res)
		f.insert(u);
	return res;
}
inline bool qq(std::deque<ll> u){
	printf("? %d %d\n",u.size(),n);
	for(auto x:u){
		for(int i=n-1;~i;i--)
			putchar('0'+((x>>i)&1));
		puts("");
	}
	fflush(stdout);
	static int res;
	scanf("%d",&res);
	return res;
}

std::vector<ll> p;
std::set<pii> s;
std::map<pii,bool> vis;
inline void sol(pii u){
	int y=u.first;ll x=u.second;
	for(;y<n;y++)
		if(qry({y+1,x<<1}))
			x<<=1;
		else if(qry({y+1,x<<1|1}))
			(x<<=1)|=1;
		else break;
	for(;y<n;y++)
		if(qry({y+1,x|(1ll<<y)}))
			x|=1ll<<y;
	p.push_back(x);
	for(;y;y--,x>>=1)
		for(int i=1;i<=y;i++){
			auto tmp=std::make_pair(i,x&((1ll<<i)-1));
			vis[tmp]=1;
			s.insert(tmp);
		}
}

std::deque<ll> q;

int main(){
	scanf("%d",&n);
	s.insert({0,0});
	while(s.size()){
		int y=s.begin()->first;
		ll x=s.begin()->second;
		s.erase(s.begin());
		if(y==n)
			continue;
		if(!vis[{y+1,x<<1}]&&qry({y+1,x<<1}))
			sol({y+1,x<<1});
		if(!vis[{y+1,x<<1|1}]&&qry({y+1,x<<1|1}))
			sol({y+1,x<<1|1});
	}
	q.push_back(p[0]);
	while(q.size()<n){
		bool flg=0;
		for(auto x:p){
			q.push_back(x);
			if(qq(q)){
				flg=1;
				break;
			}
			q.pop_back();
		}
		if(!flg)
			break;
	}
	while(q.size()<n){for(auto x:p){q.push_front(x);
			if(qq(q))break;
			q.pop_front();
		}
	}
	puts("!");
	for(auto x:q){for(int i=n-1;~i;i--)putchar('0'+((x>>i)&1));puts("");}
}

Details

Test #1:

score: 100
Accepted
time: 1ms
memory: 3736kb

Test #2:

score: 0
Accepted
time: 1ms
memory: 3760kb

Test #3:

score: 0
Accepted
time: 0ms
memory: 3696kb

Test #4:

score: 0
Accepted
time: 1ms
memory: 3740kb

Test #5:

score: 0
Accepted
time: 0ms
memory: 3760kb

Test #6:

score: 0
Accepted
time: 1ms
memory: 3788kb

Test #7:

score: 0
Accepted
time: 1ms
memory: 3700kb

Test #8:

score: 0
Accepted
time: 1ms
memory: 3692kb

Test #9:

score: 0
Accepted
time: 1ms
memory: 3696kb

Test #10:

score: 0
Accepted
time: 3ms
memory: 3800kb

Test #11:

score: 0
Accepted
time: 0ms
memory: 3712kb

Test #12:

score: 0
Accepted
time: 23ms
memory: 4748kb

Test #13:

score: 0
Accepted
time: 1ms
memory: 3780kb

Test #14:

score: 0
Accepted
time: 11ms
memory: 4948kb

Test #15:

score: 0
Accepted
time: 10ms
memory: 5152kb

Test #16:

score: 0
Accepted
time: 138ms
memory: 13364kb

Test #17:

score: 0
Accepted
time: 141ms
memory: 13316kb

Test #18:

score: 0
Accepted
time: 117ms
memory: 13380kb

Test #19:

score: 0
Accepted
time: 134ms
memory: 13396kb

Test #20:

score: 0
Accepted
time: 110ms
memory: 12884kb

Test #21:

score: 0
Accepted
time: 134ms
memory: 13000kb

Test #22:

score: 0
Accepted
time: 131ms
memory: 12924kb

Test #23:

score: 0
Accepted
time: 108ms
memory: 11464kb

Test #24:

score: 0
Accepted
time: 105ms
memory: 11656kb

Test #25:

score: 0
Accepted
time: 117ms
memory: 11884kb

Test #26:

score: 0
Accepted
time: 117ms
memory: 12788kb

Test #27:

score: 0
Accepted
time: 140ms
memory: 12876kb

Test #28:

score: 0
Accepted
time: 107ms
memory: 10780kb

Test #29:

score: 0
Accepted
time: 155ms
memory: 13408kb

Test #30:

score: 0
Accepted
time: 126ms
memory: 13304kb

Test #31:

score: 0
Accepted
time: 160ms
memory: 13384kb

Test #32:

score: 0
Accepted
time: 146ms
memory: 13344kb

Test #33:

score: 0
Accepted
time: 141ms
memory: 13380kb

Test #34:

score: 0
Accepted
time: 126ms
memory: 13400kb

Test #35:

score: 0
Accepted
time: 105ms
memory: 9252kb