oj.uz

Submission #173643

# Submission time Handle Problem Language Result Execution time Memory
173643 2020-01-04T18:58:24 Z Ruxandra985 ICC (CEOI16_icc) C++14
0 / 100
 6 ms 504 KB 
#include <bits/stdc++.h>
#include "icc.h"
using namespace std;


int f[110] , w[110] , a[110] , b[110];

void run (int n){
    int i , cc , st , dr , mid , aux , p , q , l , r , elem;

    for (i=1;i<=n;i++)
        f[i] = i;

    for (int mc = 1 ; mc < n ; mc++){
        elem = 0;
        for (cc = 1 ; cc <= n - mc + 1 ; cc++){
            for (i=1;i<=n;i++){
                if (f[i] == cc)
                    w[++elem] = i;
            }
        }

        /// w e vectorul pe care fac eu query urile

        st = 1; /// st ... dr e intervalul in indici
        dr = n;

        l = 1; /// l .. r e intervalul in "indici ai padurilor"
        r = n - mc + 1;

        /// vreau sa ma duc in jos cat pot pana gasesc intervalul care contine capetele

        while (true){

            mid = (l + r)/2;

            /// de la st la mid intr o parte, de la mid+1 la dr in alta pt

            for (i = st ; f[ w[ i ] ] <= mid ; i++)
                a[i - st] = w[i];

            aux = i; /// i ar fi primul din a doua jumatate

            for ( ; i <= dr ; i++)
                b[i - aux] = w[i];

            if (query( aux - 1 - st + 1  , dr - aux + 1 , a , b ) == 1){
                /// un capat de muchie e intr o jumatate , celalalt capat in cealalta
                p = aux - 1 - st + 1;
                q = dr - aux + 1;
                break;
            }
            else {
                /// ambele capete sunt in aceeasi jum
                b[0] = w[dr];

                if (query( aux - 1 - st + 1  , 1 , a , b ) == 0){
                    /// ambele sunt in a
                    r = mid;
                    dr = aux - 1;
                }
                else {
                    /// ambele sunt in b
                    l = mid + 1;
                    st = aux;
                }

            }

        }

        /// ai vectorii a si b
        /// a are p elem si b are q
        /// a si b sunt indexate de la 0

        /// pt a

        while (p > 1){

            if (query (p / 2 , q , a , b) == 1)
                p/=2;
            else {
                for (i = p/2 ; i < p ; i++)
                    a[i - p/2] = a[i];
                p = p - p / 2;
            }

        }

        /// pt b

        while (q > 1){

            if (query (p , q / 2 , a , b) == 1)
                q/=2;
            else {
                for (i = q/2 ; i < q ; i++)
                    b[i - q/2] = b[i];
                q = q - q / 2;
            }

        }

        setRoad(a[0] , b[0]);

        /// acum trebuie sa modificam f ul

        int u1 = f[a[0]];
        int u2 = f[b[0]];

        for (i=1;i<=n;i++){
            if (f[i] == u2)
                f[i] = u1;
            else if (f[i] == n - mc + 1)
                f[i] = u2;
        }


    }


}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 504 KB The query sets must be disjoint
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 504 KB The query sets must be disjoint
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 504 KB The query sets must be disjoint
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 504 KB The query sets must be disjoint
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 504 KB The query sets must be disjoint
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 504 KB The query sets must be disjoint
2 Halted 0 ms 0 KB -