oj.uz

Submission #990555

# Submission time Handle Problem Language Result Execution time Memory
990555 2024-05-30T16:05:36 Z alexdd Mađioničar (COI22_madionicar) C++17
38 / 100
 5000 ms 1528 KB 
#include<bits/stdc++.h>
using namespace std;
int n,cntq;

string s;
bool verif(int le, int ri)
{
    for(int i=0;i<=ri-le;i++)
        if(s[le+i]!=s[ri-i])
            return 0;
    return 1;
}

int p[100005];
bool query(int le, int ri)
{
    if(le<1 || ri>n || le>ri)
        return 0;
    if(le==ri)
        return 1;
    cntq++;
    //return verif(le,ri);
    if(cntq>200000)
    {
        while(1);
    }
    int aux;
    cout<<"? "<<le<<" "<<ri<<endl;
    cin>>aux;
    return aux;
}
signed main()
{
    cin>>n;

    /*s.resize(n+2);
    for(int i=1;i<=n;i++)
    {
        int c = rand()%26;
        s[i] = c+'a';
    }*/

    int le=1,ri=1,mxm=1;
    for(int i=1;i<=n;i++)
    {
        p[i] = max(max(0,mxm/2-5), 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(max(0,mxm/2-5), 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;
   // cout<<cntq<<" queries\n";
    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 76 ms 596 KB Output is correct
2 Correct 85 ms 704 KB Output is correct
3 Correct 67 ms 588 KB Output is correct
4 Correct 65 ms 444 KB Output is correct
5 Correct 75 ms 344 KB Output is correct
6 Correct 72 ms 448 KB Output is correct
7 Correct 71 ms 448 KB Output is correct
8 Correct 48 ms 592 KB Output is correct
9 Correct 86 ms 672 KB Output is correct
10 Correct 76 ms 592 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 596 KB Output is correct
2 Correct 85 ms 704 KB Output is correct
3 Correct 67 ms 588 KB Output is correct
4 Correct 65 ms 444 KB Output is correct
5 Correct 75 ms 344 KB Output is correct
6 Correct 72 ms 448 KB Output is correct
7 Correct 71 ms 448 KB Output is correct
8 Correct 48 ms 592 KB Output is correct
9 Correct 86 ms 672 KB Output is correct
10 Correct 76 ms 592 KB Output is correct
11 Correct 799 ms 960 KB Output is correct
12 Correct 781 ms 764 KB Output is correct
13 Correct 841 ms 1084 KB Output is correct
14 Correct 790 ms 592 KB Output is correct
15 Correct 761 ms 592 KB Output is correct
16 Correct 613 ms 1216 KB Output is correct
17 Correct 569 ms 956 KB Output is correct
18 Correct 803 ms 1108 KB Output is correct
19 Correct 556 ms 1528 KB Output is correct
20 Correct 775 ms 1224 KB Output is correct
21 Correct 754 ms 1272 KB Output is correct
22 Correct 802 ms 1080 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5073 ms 1284 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 596 KB Output is correct
2 Correct 85 ms 704 KB Output is correct
3 Correct 67 ms 588 KB Output is correct
4 Correct 65 ms 444 KB Output is correct
5 Correct 75 ms 344 KB Output is correct
6 Correct 72 ms 448 KB Output is correct
7 Correct 71 ms 448 KB Output is correct
8 Correct 48 ms 592 KB Output is correct
9 Correct 86 ms 672 KB Output is correct
10 Correct 76 ms 592 KB Output is correct
11 Correct 799 ms 960 KB Output is correct
12 Correct 781 ms 764 KB Output is correct
13 Correct 841 ms 1084 KB Output is correct
14 Correct 790 ms 592 KB Output is correct
15 Correct 761 ms 592 KB Output is correct
16 Correct 613 ms 1216 KB Output is correct
17 Correct 569 ms 956 KB Output is correct
18 Correct 803 ms 1108 KB Output is correct
19 Correct 556 ms 1528 KB Output is correct
20 Correct 775 ms 1224 KB Output is correct
21 Correct 754 ms 1272 KB Output is correct
22 Correct 802 ms 1080 KB Output is correct
23 Execution timed out 5073 ms 1284 KB Time limit exceeded
24 Halted 0 ms 0 KB -