oj.uz

Submission #748938

# Submission time Handle Problem Language Result Execution time Memory
748938 2023-05-27T07:30:32 Z 반딧불(#9966) Mađioničar (COI22_madionicar) C++17
0 / 100
 79 ms 1040 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 || (r+1)/2-(l+1)/2+1 <= ans) 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 = arr[m];
            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]+1; i+l<=n+1 && i-l>=0; l++){
                    if(!query(i-l, i+l)) break;
                    arr[q] = l;
                }
            }
        }
        if(maxV < i+arr[i]) maxV = i+arr[i], maxMid = i;
        ans = max(ans, arr[i]);
    }

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

Compilation message

Main.cpp: In function 'bool query(int, int)':
Main.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     scanf("%d", &x);
      |     ~~~~~^~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 340 KB L = 17, expected 30
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 340 KB L = 17, expected 30
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 79 ms 1040 KB L = 34, expected 52
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 340 KB L = 17, expected 30
2 Halted 0 ms 0 KB -