oj.uz

Submission #748944

# Submission time Handle Problem Language Result Execution time Memory
748944 2023-05-27T07:45:54 Z 반딧불(#9966) Mađioničar (COI22_madionicar) C++17
0 / 100
 1284 ms 1356 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((n-(i*2-n))/2+1 < ans) break;
        if(maxV < i){ /// �ٱ����̶� �� �� ���� ���
            for(int l=1; i+l<=n+1 && i-l>=1; 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>=1; 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 Correct 99 ms 376 KB Output is correct
2 Correct 67 ms 424 KB Output is correct
3 Correct 117 ms 344 KB Output is correct
4 Correct 117 ms 464 KB Output is correct
5 Correct 166 ms 340 KB Output is correct
6 Correct 143 ms 428 KB Output is correct
7 Incorrect 114 ms 428 KB L = 7499, expected 7500
8 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 376 KB Output is correct
2 Correct 67 ms 424 KB Output is correct
3 Correct 117 ms 344 KB Output is correct
4 Correct 117 ms 464 KB Output is correct
5 Correct 166 ms 340 KB Output is correct
6 Correct 143 ms 428 KB Output is correct
7 Incorrect 114 ms 428 KB L = 7499, expected 7500
8 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1284 ms 1356 KB Output is correct
2 Correct 972 ms 1124 KB Output is correct
3 Incorrect 1054 ms 1060 KB L = 4793, expected 4794
4 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 376 KB Output is correct
2 Correct 67 ms 424 KB Output is correct
3 Correct 117 ms 344 KB Output is correct
4 Correct 117 ms 464 KB Output is correct
5 Correct 166 ms 340 KB Output is correct
6 Correct 143 ms 428 KB Output is correct
7 Incorrect 114 ms 428 KB L = 7499, expected 7500
8 Halted 0 ms 0 KB -