QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#35760#4306. Guess MatrixQingyuWA 19ms5084kbC++1.8kb2022-06-18 20:51:522023-09-13 18:58:21

Judging History

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

  • [2023-09-13 18:58:21]
  • 管理员手动重测该提交记录
  • 测评结果:WA
  • 用时:19ms
  • 内存:5084kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-06-18 20:51:53]
  • 评测
  • 测评结果:0
  • 用时:94ms
  • 内存:5172kb
  • [2022-06-18 20:51:52]
  • 提交

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|(1<<y)}))
			x|=1<<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: 3704kb

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

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

Test #12:

score: 0
Accepted
time: 19ms
memory: 4724kb

Test #13:

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

Test #14:

score: 0
Accepted
time: 15ms
memory: 4932kb

Test #15:

score: -100
Wrong Answer
time: 17ms
memory: 5084kb