oj.uz

Submission #173855

# Submission time Handle Problem Language Result Execution time Memory
173855 2020-01-05T14:42:17 Z Ruxandra985 ICC (CEOI16_icc) C++14
90 / 100
 162 ms 636 KB 
#include <bits/stdc++.h>
#include "icc.h"
using namespace std;


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

void run (int n){
    int i , p , q , bit;
    for (i=1;i<=n;i++)
        f[i] = i;

    for (int mc = 1 ; mc < n ; mc++){

        memset ( fq , 0 , sizeof (fq));
        /// vreau sa ma duc in jos cat pot pana gasesc intervalul care contine capetele
        bit = 0;
        int tryy = 0;
        while (true){

            /// o sa fac solutia aia mai proasta cu generat random pt ca nuj cum altcumva
            int nr = rand() % (7 - tryy) + 1;
            tryy++;
            i = 0;
            while (nr){ /// al nr -lea care e 0
                if (!fq[i])
                    nr--;
                if (!nr){
                    bit = i;
                    break;
                }
                i++;
            }
            fq[bit] = 1;
            p = q = 0;
            for (i=1;i<=n;i++){
                if (f[i] & (1 << bit))
                    a[p++] = i;
            }

            for (i=1;i<=n;i++){
                if ((f[i] & (1 << bit)) == 0)
                    b[q++] = i;
            }


            if (query( p , q , a , b ) == 1){
                /// un capat de muchie e intr o jumatate , celalalt capat in cealalta
                break;
            }
            else {
                /// ambele capete sunt in aceeasi jum
                continue;

            }

        }

        /// 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 = min( f[a[0]] , f[b[0]] );
        int u2 = max( f[a[0]] , f[b[0]] );

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


    }


}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 504 KB Ok! 115 queries used.
2 Correct 8 ms 504 KB Ok! 112 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 504 KB Ok! 581 queries used.
2 Correct 51 ms 632 KB Ok! 775 queries used.
3 Correct 50 ms 584 KB Ok! 753 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 564 KB Ok! 1527 queries used.
2 Correct 162 ms 548 KB Ok! 1795 queries used.
3 Correct 148 ms 588 KB Ok! 1705 queries used.
4 Correct 144 ms 504 KB Ok! 1655 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 552 KB Ok! 1710 queries used.
2 Correct 149 ms 636 KB Ok! 1740 queries used.
3 Correct 151 ms 552 KB Ok! 1763 queries used.
4 Correct 142 ms 632 KB Ok! 1605 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 504 KB Ok! 1738 queries used.
2 Correct 159 ms 548 KB Ok! 1737 queries used.
3 Correct 159 ms 632 KB Ok! 1772 queries used.
4 Correct 150 ms 564 KB Ok! 1760 queries used.
5 Correct 141 ms 504 KB Ok! 1606 queries used.
6 Correct 147 ms 632 KB Ok! 1670 queries used.

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 155 ms 556 KB Too many queries! 1758 out of 1625
2 Halted 0 ms 0 KB -