Location>code7788 >text

Codeforces Round 988 (Div. 3) E Question Analysis

Popularity:424 ℃/2024-11-18 17:17:04

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;
}
/*

*/