oj.uz

Submission #1030698

# Submission time Handle Problem Language Result Execution time Memory
1030698 2024-07-22T08:45:32 Z 12345678 Colors (BOI20_colors) C++17
0 / 100
 0 ms 344 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=100;

int n, tmp, l, r, t, lst, x, ql[nx], qr[nx], dp[nx], used[nx], C, pv=-1;

int query(int x)
{
    if (pv==-1) return pv=x, 0;
    tmp=abs(x-pv);
    pv=x;
    return tmp>=C;
    cout<<"? "<<x<<endl;
    cin>>tmp;
    return tmp;
}

int main()
{
    cin>>n;
    cin>>C;
    if (n<=64)
    {
        l=1, r=n+1;
        query(1);
        for (int i=1; i<n; i++)
        {
            if (i%2) r--, dp[r-l]=query(r);
            else l++, dp[r-l]=query(l);
        }
        for (int i=1; i<=n; i++) if (dp[i]) return cout<<"= "<<i, 0;
        return cout<<"= "<<n, 0;
    }
    l=1, r=n+1;
    for (int i=1; i<64; i++)
    {
        if (i%2) r--;
        else l++;
        ql[i]=l;
        qr[i]=r;
    }
    query(qr[63]);
    lst=ql[63];
    used[ql[63]]=used[qr[63]]=1;
    if (!query(ql[63]))
    {
        for (int i=62; i>=1; i--)
        {
            if (ql[i]==lst) lst=qr[i], t=query(qr[i]);
            else lst=ql[i], t=query(ql[i]);
            if (t) return cout<<"= "<<n-i, 0;
        }
        return cout<<"= "<<n, 0;
    }
    l=1, r=n-63;
    while (l<r)
    {
        int md=(l+r)/2;
        //cout<<"debug "<<l<<' '<<r<<' '<<md<<'\n';
        for (int i=1; i+md<=n; i++)
        {
            if (!used[i]&&!used[i+md])
            {
                query(i);
                t=query(i+md);
                used[i]=used[i+md]=1;
                break;
            }
        }
        if (t) r=md;
        else l=md+1;
    }
    cout<<"= "<<l, 0;
}

Compilation message

Colors.cpp: In function 'int main()':
Colors.cpp:75:21: warning: right operand of comma operator has no effect [-Wunused-value]
   75 |     cout<<"= "<<l, 0;
      |                     ^

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 0 ms 344 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 0 ms 344 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 0 ms 344 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 0 ms 344 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Execution timed out 0 ms 344 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -