Question E
Title Link
Codeforces Round 988 (Div. 3)
Title Description
Thoughts on the topic
Based on the meaning of the title, we can infer that the algorithm time complexity should be O(N)
For this question, we can analyze the following ideas
First we start by asking for the answer from inside the range 1 to n
Skip if 0 occurs because of the unordered operation
If a non-zero answer temp occurs record the number of 01 sequences from 1 to i
If all the answers to my query are 0, then my sequence must be all 0s or all 1s, which is impossible to determine, so we can output "IMPOSSIBLE".
Otherwise we can construct goal substrings that satisfy the non-zero answer temp
We can put i-temp-1 1, then temp 0, then 1 1, this 1 can and the previous temp 0 to form temp 01 sequence
Then the answer is asked for the range i+1~n, and the queried answer is labeled as now, and the answer of the last query is indicated by temp
Here's an example of an answer that comes out of a positive-order query
If the answer is greater than the previous answer, it means that it needs to be increased, so we add "1" to ans, and this operation will be combined with the previous 0 to form a 01 sequence.
If the answer to the query remains unchanged, then it means that there is no need to increase, add "0" to the end of the ans, this 1 and the previous "0" or "1" will not form the 01 sequence.
Just output it at the end
AC code
inverse search(Judging the logic of the answer is the opposite of the positive order, since the constructed answer is reversed)
Click to view code
// Problem: E. Kachina's Favorite Binary String
// Contest: Codeforces - Codeforces Round 988 (Div. 3)
// URL: /contest/2037/problem/E#
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor ()
#include <bits/stdc++.h>
#define debug1(a) cout << #a << '=' << a << endl;
#define debug2(a, b) cout << #a << " = " << a << " " << #b << " = " << b << endl;
#define debug3(a, b, c) cout << #a << " = " << a << " " << #b << " = " << b << " " << #c << " = " << c << endl;
#define debug4(a, b, c, d) cout << #a << " = " << a << " " << #b << " = " << b << " " << #c << " = " << c << " " << #d << " = " << d << endl;
#define debug5(a, b, c, d, e) cout << #a << " = " << a << " " << #b << " = " << b << " " << #c << " = " << c << " " << #d << " = " << d << " " << #e << " = " << e << endl;
#define vec(a) \
for (int i = 0; i < (); i++) \
cout << a[i] << ' '; \
cout << endl;
#define darr(a, _i, _n) \
cout << #a << ':'; \
for (int ij = _i; ij <= _n; ij++) \
cout << a[ij] << ' '; \
cout << endl;
#define endl "\n"
#define fi first
#define se second
#define caseT \
int T; \
cin >> T; \
while (T--)
// #define int long long
// #define int __int128
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int MOD = 99999999;
// const int N = ;
void solve()
{
int n;
cin>>n;
int s1=0,s0=0;
int temp;
string s;
for(int i=n-1;i>=1;i--)
{
cout<<"? "<<i<<" "<<n<<endl;
cin>>temp;
if(!temp)continue;
else{
s1=temp;
s0=n-i-temp;
break;
}
}
if(!s1)
{
cout<<"! IMPOSSIBLE"<<endl;
return;
}
for(int i=1;i<=s0;i++)s+="0";
for(int i=1;i<=s1;i++)s+="1";
s+="0";
//This construction ensures that the first query comes out not as a0The answer to the question istemp
for(int i=n-s1-s0-1;i>=1;i--)
{
cout<<"? "<<i<<" "<<n<<endl;
int now;
cin>>now;
if(now>temp)s+="0";
else s+="1";
temp=now;
}
reverse((),());
cout<<"! "<<s<<endl;
}
signed main()
{
// ios::sync_with_stdio(false);
// (0);
// (0);
//caseT
int t;
cin>>t;
while(t--)
{
solve();
}
return 0;
}
/*
*/
orthogonal search
Click to view code
// Problem: E. Kachina's Favorite Binary String
// Contest: Codeforces - Codeforces Round 988 (Div. 3)
// URL: /contest/2037/problem/E#
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor ()
#include <bits/stdc++.h>
#define debug1(a) cout << #a << '=' << a << endl;
#define debug2(a, b) cout << #a << " = " << a << " " << #b << " = " << b << endl;
#define debug3(a, b, c) cout << #a << " = " << a << " " << #b << " = " << b << " " << #c << " = " << c << endl;
#define debug4(a, b, c, d) cout << #a << " = " << a << " " << #b << " = " << b << " " << #c << " = " << c << " " << #d << " = " << d << endl;
#define debug5(a, b, c, d, e) cout << #a << " = " << a << " " << #b << " = " << b << " " << #c << " = " << c << " " << #d << " = " << d << " " << #e << " = " << e << endl;
#define vec(a) \
for (int i = 0; i < (); i++) \
cout << a[i] << ' '; \
cout << endl;
#define darr(a, _i, _n) \
cout << #a << ':'; \
for (int ij = _i; ij <= _n; ij++) \
cout << a[ij] << ' '; \
cout << endl;
#define endl "\n"
#define fi first
#define se second
#define caseT \
int T; \
cin >> T; \
while (T--)
// #define int long long
// #define int __int128
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int MOD = 99999999;
// const int N = ;
void solve()
{
int n;
cin>>n;
int temp=0;//The record is the result of the last query
int p=0;//Whether or not the marker has changed
vector<int>ans(n+1);
for(int i=2;i<=n;i++)
{
cout<<"? "<<1<<" "<<i<<endl;
int x;
cin>>x;
if(x&&!p)//If the answer to the query is greater than0And it hasn't changed.
{
for(int j=1;j<i-x;j++)ans[j]=1;
for(int j=i-x;j<i;j++)ans[j]=0;
ans[i]=1;
p=1;
}else{
if(x==temp)ans[i]=0;
else ans[i]=1;
}
temp=x;
}
cout<<"! ";
if(!p)cout<<"IMPOSSIBLE"<<endl;
else{
for(int i=1;i<=n;i++)cout<<ans[i];
cout<<endl;
}
}
signed main()
{
// ios::sync_with_stdio(false);
// (0);
// (0);
//caseT
int t;
cin>>t;
while(t--)
{
solve();
}
return 0;
}
/*
*/