QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#43102#4306. Guess MatrixperspectiveAC ✓360ms13540kbC++171.8kb2022-08-07 17:48:232022-08-07 17:48:24

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-08-07 17:48:24]
  • 评测
  • 测评结果:AC
  • 用时:360ms
  • 内存:13540kb
  • [2022-08-07 17:48:23]
  • 提交

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: 4ms
memory: 3808kb

Test #2:

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

Test #3:

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

Test #4:

score: 0
Accepted
time: 4ms
memory: 3704kb

Test #5:

score: 0
Accepted
time: 4ms
memory: 3816kb

Test #6:

score: 0
Accepted
time: 4ms
memory: 3824kb

Test #7:

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

Test #8:

score: 0
Accepted
time: 5ms
memory: 3872kb

Test #9:

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

Test #10:

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

Test #11:

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

Test #12:

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

Test #13:

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

Test #14:

score: 0
Accepted
time: 101ms
memory: 5060kb

Test #15:

score: 0
Accepted
time: 46ms
memory: 5060kb

Test #16:

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

Test #17:

score: 0
Accepted
time: 314ms
memory: 13296kb

Test #18:

score: 0
Accepted
time: 351ms
memory: 13500kb

Test #19:

score: 0
Accepted
time: 350ms
memory: 13476kb

Test #20:

score: 0
Accepted
time: 318ms
memory: 13084kb

Test #21:

score: 0
Accepted
time: 324ms
memory: 13076kb

Test #22:

score: 0
Accepted
time: 269ms
memory: 13036kb

Test #23:

score: 0
Accepted
time: 257ms
memory: 11504kb

Test #24:

score: 0
Accepted
time: 356ms
memory: 11700kb

Test #25:

score: 0
Accepted
time: 297ms
memory: 11948kb

Test #26:

score: 0
Accepted
time: 359ms
memory: 12900kb

Test #27:

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

Test #28:

score: 0
Accepted
time: 277ms
memory: 10852kb

Test #29:

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

Test #30:

score: 0
Accepted
time: 275ms
memory: 13540kb

Test #31:

score: 0
Accepted
time: 346ms
memory: 13504kb

Test #32:

score: 0
Accepted
time: 360ms
memory: 13472kb

Test #33:

score: 0
Accepted
time: 358ms
memory: 13376kb

Test #34:

score: 0
Accepted
time: 305ms
memory: 13476kb

Test #35:

score: 0
Accepted
time: 224ms
memory: 9328kb