QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#43101#4306. Guess MatrixperspectiveWA 101ms5216kbC++171.8kb2022-08-07 17:13:162022-08-07 17:13:18

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:13:18]
  • 评测
  • 测评结果:WA
  • 用时:101ms
  • 内存:5216kb
  • [2022-08-07 17:13:16]
  • 提交

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("");}
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 3856kb

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

score: 0
Accepted
time: 7ms
memory: 3852kb

Test #11:

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

Test #12:

score: 0
Accepted
time: 28ms
memory: 4804kb

Test #13:

score: 0
Accepted
time: 12ms
memory: 3852kb

Test #14:

score: 0
Accepted
time: 32ms
memory: 5064kb

Test #15:

score: -100
Wrong Answer
time: 101ms
memory: 5216kb