oj.uz

Submission #856197

# Submission time Handle Problem Language Result Execution time Memory
856197 2023-10-02T19:19:54 Z Benmath popa (BOI18_popa) C++14
61 / 100
 423 ms 676 KB 
/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/
#include<popa.h>
#include <bits/stdc++.h>

using namespace std;
using pii = pair<int,pair<int,int>>;
int solver(int prvi, int drugi, int lijevo[], int desno[]){
    for(int i = prvi; i <= drugi; i++){
        if(lijevo[i] <= prvi and drugi <= desno[i]){
            return i;
        }
    }
}

int solve(int N, int* Left, int* Right){
    int n = N;
    int lijevo[n];
    int desno[n];
    for(int i = 0; i < n; i++){
        Left[i] = -1;
        Right[i] = -1;
       lijevo[i] = i;
       int l = 0;
       int r = i - 1;
       while(l <= r){
           int mid = (l + r)/2;
           if(query(mid, i, i, i) == 1){
               lijevo[i] = min(lijevo[i] , mid);
               r = mid - 1;
           }else{
               l = mid + 1;
           }
       }
       l = i + 1;
       desno[i] = i;
       r = n - 1;
       while(l <= r){
           int mid = (l + r)/2;
           if(query(i,mid, i, i) == 1){
               desno[i] = max(desno[i], mid);
               l = mid + 1;
           }else{
               r = mid - 1;
           }
       }
       
    }
    int root = solver(0,n - 1, lijevo, desno);
    int interval1 = 0;
    queue<pair<int,pair<int,int>>>q;
    q.push({root,{0, n - 1}});
    while(!q.empty()){
        pii a = q.front();
        q.pop();
        int trenutni = a.first;
        int prvi = a.second.first;
        int drugi = a.second.second;
        if(prvi < trenutni){
            int x = solver(prvi, trenutni - 1, lijevo, desno);
            Left[trenutni] = x;
            q.push({x,{prvi,trenutni - 1}});
        }
        if(trenutni < drugi){
            
            int x = solver(trenutni + 1, drugi, lijevo,desno);
            
            Right[trenutni] = x;
            q.push({x,{trenutni + 1, drugi}});
        }
    }
    return root;
    
}

Compilation message

popa.cpp: In function 'int solve(int, int*, int*)':
popa.cpp:55:9: warning: unused variable 'interval1' [-Wunused-variable]
   55 |     int interval1 = 0;
      |         ^~~~~~~~~
popa.cpp: In function 'int solver(int, int, int*, int*)':
popa.cpp:19:1: warning: control reaches end of non-void function [-Wreturn-type]
   19 | }
      | ^

Subtask #1
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 344 KB Output is correct
2 Correct 22 ms 340 KB Output is correct
3 Correct 24 ms 344 KB Output is correct
4 Correct 22 ms 344 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 423 ms 428 KB Output is correct
2 Correct 402 ms 676 KB Output is correct
3 Correct 239 ms 428 KB Output is correct
4 Correct 369 ms 592 KB Output is correct

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 344 KB too many queries
2 Halted 0 ms 0 KB -