Submission #1359564

#TimeUsernameProblemLanguageResultExecution timeMemory
1359564uwuDark Ride (EGOI25_darkride)C++20
0 / 100
0 ms420 KiB
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
//#define double long double

#define PI acos(-1)
int MOD = 10000000000000007;
bool prime(int n){
    if(n < 2)return false;
    for(int i = 2;i * i<= n;i++){
        if(n % i == 0){
            return false;
        }
    }
    return true;
}
bool comp(pair<int,int> a,pair<int,int> b){
    return a.first < b.first;
}

struct seggy {
    int n;
    vector<int> tree, lazy;
    const int NEUTRAL = 0;                 
    int merge(int a, int b) { return (a+b); }

    seggy(int size) {
        n = size;
        tree.assign(4*n, NEUTRAL);
        lazy.assign(4*n, 0);
    }

    void build(vector<int>& arr, int node, int l, int r) {
        if (l == r) {
            tree[node] = arr[l];
        } else {
            int mid = (l + r) / 2;
            build(arr, 2*node, l, mid);
            build(arr, 2*node+1, mid+1, r);
            tree[node] = merge(tree[2*node], tree[2*node+1]);
        }
    }

    void push(int node, int l, int r) {
        if (lazy[node] != 0) {
            tree[node] += lazy[node];

            if (l != r) {
                lazy[2*node] += lazy[node];
                lazy[2*node+1] += lazy[node];
            }

            lazy[node] = 0;
        }
    }

    void update(int node, int l, int r, int ql, int qr, int val) {
        push(node, l, r);

        if (r < ql || l > qr) return;

        if (ql <= l && r <= qr) {
            lazy[node] += val;
            push(node, l, r);
            return;
        }

        int mid = (l + r) / 2;
        update(2*node, l, mid, ql, qr, val);
        update(2*node+1, mid+1, r, ql, qr, val);

        tree[node] = merge(tree[2*node], tree[2*node+1]);
    }

    int query(int node, int l, int r, int ql, int qr) {
        push(node, l, r);
        if (r < ql || l > qr) return NEUTRAL;
        if (ql <= l && r <= qr) return tree[node];

        int mid = (l + r) / 2;
        return merge(
            query(2*node, l, mid, ql, qr),
            query(2*node+1, mid+1, r, ql, qr)
        );
    }
    void build(vector<int>& arr) {
        build(arr, 1, 0, n-1);
    }

    void update(int l, int r, int val) {
        update(1, 0, n-1, l, r, val);
    }

    int query(int l, int r) {
        return query(1, 0, n-1, l, r);
    }
};
int modinverse(int A, int M)
{
    int m0 = M;
    int y = 0, x = 1;

    if (M == 1)
        return 0;

    while (A > 1) {
        // q is quotient
        int q = A / M;
        int t = M;

        // m is remainder now, process same as
        // Euclid's algo
        M = A % M, A = t;
        t = y;

        // Update y and x
        y = x - q * y;
        x = t;
    }

    // Make x positive
    if (x < 0)
        x += m0;

    return x;
}
void solve();
signed main(){
    //ios_base::sync_with_stdio(0);
    //cin.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout); 
    int t;
    t = 1;
    //cin>>t;
    while(t--){
        solve();
    }
}


void solve(){
    int n;cin>>n;
    int l = 0;
    int u = n;
    while(u-l > 1){
        int bs = (u+l)/2;
        vector<char> ans(n);
        /*(for(int i = l;i < bs;i++){
            ans[i] = '1';
        }
        for(int i = bs;i < n;i++){
            ans[i] = '0';
        }*/
        for(int i = 0;i < n;i++){
            if(i >= l && i < bs)ans[i] = '1';
            else ans[i] = '0';
        }
        for(auto i : ans)cout<<i;
        cout<<endl;
        cout.flush();
        int v;cin>>v;
        if(v % 2 == 1)u = bs;
        else l = bs;
    }
    int uwu1 = l;
    u = n;
    l = 0;
    while(u-l > 1){
        int bs = (u+l)/2;
        vector<char> ans(n);
        /*
        for(int i = l;i < bs;i++){
            ans[i] = '0';
        }
        for(int i = bs;i < n;i++){
            ans[i] = '1';
        }*/
        for(int i = 0;i < n;i++){
            if(i >= bs && i < u)ans[i] = '1';
            else ans[i] = '0';
        }
        for(auto i : ans)cout<<i;
        cout<<endl;
        cout.flush();
        int v;cin>>v;
        if(v % 2 == 1)u = bs;
        else l = bs;
    }
    int uwu2 = l;
    cout<<"! "<<uwu1<<" "<<uwu2<<endl;
    cout.flush();
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...