oj.uz

Submission #748880

# Submission time Handle Problem Language Result Execution time Memory
748880 2023-05-27T06:16:55 Z 반딧불(#9966) Mađioničar (COI22_madionicar) C++17
0 / 100
 662 ms 1012 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
int arr[200002];
int ans;

bool query(int l, int r){
    assert(l%2 == r%2);
    if(l%2==0) return true;
    printf("? %d %d\n", (l+1)/2, (r+1)/2);
    fflush(stdout);
    int x;
    scanf("%d", &x);
    return x;
}

int main(){
    scanf("%d", &n);
    n = 2*n-1;
    int maxV = 0, maxMid = 0;
    for(int i=1; i<=n; i++){
        if(maxV < i){ /// �ٱ����̶� �� �� ���� ���
            for(int l=1; i+l<=n+1 && i-l>=0; l++){
                if(!query(i-l, i+l)) break;
                arr[i] = l;
            }
        }
        else{ /// ������ ���
            int m = maxMid, mlen = maxV;
            int l = maxMid-mlen, r = maxMid+mlen;
            int q = i, p = m+m-q, plen = arr[p];
            if(p-plen > l) arr[q] = arr[p];
            else if(p-plen < l) arr[q] = r-q;
            else{
                arr[q] = p-l;
                for(int l=arr[q]; i+l<=n+1 && i-l>=0; l++){
                    if(!query(i-l, i+l)) break;
                    arr[i] = l;
                }
            }
        }
        maxV = max(maxV, i+arr[i]);
    }

    for(int i=1; i<=n; i++){
        if(i%2) ans = max(ans, arr[i]);
        else    ans = max(ans, arr[i]);
    }

    printf("! %d", ans);
}

Compilation message

Main.cpp: In function 'bool query(int, int)':
Main.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     scanf("%d", &x);
      |     ~~~~~^~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
Main.cpp:35:47: warning: array subscript -1 is below array bounds of 'int [200002]' [-Warray-bounds]
   35 |             int q = i, p = m+m-q, plen = arr[p];
      |                                          ~~~~~^
Main.cpp:8:5: note: while referencing 'arr'
    8 | int arr[200002];
      |     ^~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 440 KB Integer 2147483647 violates the range [1, 7500]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 440 KB Integer 2147483647 violates the range [1, 7500]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 662 ms 1012 KB Integer 2147483647 violates the range [1, 100000]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 440 KB Integer 2147483647 violates the range [1, 7500]
2 Halted 0 ms 0 KB -