oj.uz

Submission #990550

# Submission time Handle Problem Language Result Execution time Memory
990550 2024-05-30T15:55:52 Z alexdd Mađioničar (COI22_madionicar) C++17
13 / 100
 1263 ms 1476 KB 
#include<bits/stdc++.h>
using namespace std;
int n;
int p[100005];
bool query(int le, int ri)
{
    if(le<1 || ri>n || le>ri)
        return 0;
    if(le==ri)
        return 1;
    int aux;
    cout<<"? "<<le<<" "<<ri<<endl;
    cin>>aux;
    return aux;
}
signed main()
{
    cin>>n;
    int le=1,ri=1,mxm=1;
    for(int i=1;i<n;i++)
    {
        p[i] = max(0, min(ri-i, p[le + (ri-i)]));
        while(query(i-p[i],i+p[i]))
            p[i]++;
        if(i+p[i] > ri)
        {
            le = i-p[i];
            ri = i+p[i];
        }
        mxm = max(mxm, 2*p[i]-1);
    }
    le=1;
    ri=1;
    for(int i=1;i<n;i++)
    {
        p[i] = max(0, min(ri-i-1, p[le+(ri-i)-1]));
        while(query(i-p[i],i+1+p[i]))
            p[i]++;
        if(i+1+p[i] > ri)
        {
            le = i-p[i];
            ri = i+1+p[i];
        }
        mxm = max(mxm, 2*p[i]);
    }
    cout<<"! "<<mxm<<endl;
    return 0;
}
/**
neven

1 2 3 4 5 6 7 8 9
    l       r
    a b c b a

1 2 3 4 5 6 7 8 9
    l         r
    a b c c b a
*/

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 700 KB Output is correct
2 Correct 75 ms 592 KB Output is correct
3 Correct 63 ms 592 KB Output is correct
4 Correct 181 ms 600 KB Output is correct
5 Correct 149 ms 696 KB Output is correct
6 Correct 148 ms 676 KB Output is correct
7 Correct 138 ms 600 KB Output is correct
8 Correct 119 ms 592 KB Output is correct
9 Correct 144 ms 944 KB Output is correct
10 Correct 89 ms 684 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 700 KB Output is correct
2 Correct 75 ms 592 KB Output is correct
3 Correct 63 ms 592 KB Output is correct
4 Correct 181 ms 600 KB Output is correct
5 Correct 149 ms 696 KB Output is correct
6 Correct 148 ms 676 KB Output is correct
7 Correct 138 ms 600 KB Output is correct
8 Correct 119 ms 592 KB Output is correct
9 Correct 144 ms 944 KB Output is correct
10 Correct 89 ms 684 KB Output is correct
11 Runtime error 1175 ms 1120 KB Execution killed with signal 13
12 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1263 ms 1476 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 700 KB Output is correct
2 Correct 75 ms 592 KB Output is correct
3 Correct 63 ms 592 KB Output is correct
4 Correct 181 ms 600 KB Output is correct
5 Correct 149 ms 696 KB Output is correct
6 Correct 148 ms 676 KB Output is correct
7 Correct 138 ms 600 KB Output is correct
8 Correct 119 ms 592 KB Output is correct
9 Correct 144 ms 944 KB Output is correct
10 Correct 89 ms 684 KB Output is correct
11 Runtime error 1175 ms 1120 KB Execution killed with signal 13
12 Halted 0 ms 0 KB -