Submission #607587

#	Time	Username	Problem	Language	Result	Execution time	Memory
607587		chonka	popa (BOI18_popa)	C++17	100 / 100	109 ms	412 KiB

popa

#include<bits/stdc++.h>
#include "popa.h"
using namespace std ;


int query ( int a , int b , int c , int d ) ;

pair < int , int > ranges[ 1007 ] ;
vector < int > v ;


int solve ( int n , int *Left , int *Right ) {
    for ( int i = 0 ; i < n ; ++ i ) {
        ranges[ i ] = { i , i } ;
        Left[ i ] = Right[ i ] = -1 ;
    }
    v.clear ( ) ;
    v.push_back ( -1 ) ;
    for ( int i = 0 ; i < n ; ++ i ) {
        while ( 1 ) {
            int aux = v.back ( ) ;
            if ( aux >= 0 && query ( aux , i , i , i ) == 1 ) {
                v.pop_back ( ) ;
            }
            else {
                ranges[ i ].first = aux + 1 ;
                for ( auto y : v ) {
                    if ( y != -1 ) {
                        ranges[ y ].second = i ;
                    }
                }
                break ;
            }
        }
        v.push_back ( i ) ;
    }
    int root = -1 ;
    for ( int i = 0 ; i < n ; ++ i ) {
        if ( ranges[ i ].first == 0 && ranges[ i ].second == n - 1 ) {
            root = i ;
            break ;
        }
    }
    stack < int > aux ;
    aux.push ( root ) ;
    while ( aux.empty ( ) == false ) {
        int wh = aux.top ( ) ;
        aux.pop ( ) ;
        for ( int i = 0 ; i < n ; ++ i ) {
            if ( ranges[ i ].first == ranges[ wh ].first && ranges[ i ].second == wh - 1 ) {
                Left[ wh ] = i ;
            }
            if ( ranges[ i ].first == wh + 1 && ranges[ i ].second == ranges[ wh ].second ) {
                Right[ wh ] = i ;
            }
        }
        if ( Left[ wh ] != -1 ) {
            aux.push ( Left[ wh ] ) ;
        }
        if ( Right[ wh ] != -1 ) {
            aux.push ( Right[ wh ] ) ;
        }
    }
    return root ;
}

• Subtask 1: 37 / 37
• Subtask 2: 24 / 24
• Subtask 3: 39 / 39