Submission #173871

#	Time	Username	Problem	Language	Result	Execution time	Memory
173871		Ruxandra985	ICC (CEOI16_icc)	C++14	100 / 100	149 ms	688 KiB

icc

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


int f[110] , w[110] , a[110] , b[110] , idk[110] , b2[110] , a2[110] , nope[110];
int ca[110] , cb[110] , logg[110];

void run (int n){
    int i , p , q , bit , en , elem , j , p2 , q2 , ea , eb , k;
    logg[0] = -1;
    for (i=1;i<=n;i++){
        f[i] = i;
        logg[i] = 1 + logg[i/2];
    }

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

        //if (mc == 4)
          //  printf ("a");
        /// vreau sa ma duc in jos cat pot pana gasesc intervalul care contine capetele
        bit = 0;
        en = elem = 0;
        while (bit <= logg[n - mc + 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
                idk[++elem] = bit; /// bitul bit e diferit in comp(x) si comp(y)
            }
            else nope[++en] = bit; /// sunt la fel
            bit++;
        }
        memset (a , 0 , sizeof(a));
        memset (a2 , 0 , sizeof(a2));
        memset (b , 0 , sizeof(b));
        memset (b2 , 0 , sizeof(b2));
        //if (mc == 4)
          //  printf ("a");
        p = q = n - mc + 1;
        for (i=0;i<n - mc + 1;i++){
            a[i] = b[i] = i + 1;
        }
        for (i = 1 ; i <= elem ; i++){

            for (j=0;j<p;j++){
                a2[j] = a[j];
            }
            for (j=0;j<q;j++){
                b2[j] = b[j];
            }
            p2 = p;
            q2 = q;
            /// in a le punem pe alea cu 1 , in b pe alea cu 0
            for (j = 0 ; j < p2 ; j++){
                if ( (a2[j] & (1 << idk[i])) ==0 ){ /// asta are 0 , nu e ok
                    swap(a2[p2 - 1] , a2[j]);
                    p2--;
                    j--;
                }
            }

            for (j = 0 ; j < q2 ; j++){
                if ( (b2[j] & (1 << idk[i])) != 0 ){ /// asta are 1 , nu e ok
                    swap(b2[q2 - 1] , b2[j]);
                    q2--;
                    j--;
                }
            }
            /// in a2 ti au ramas cele cu configuratie fixata + 1
            /// in b2 ti au ramas cu configuratie fixata + 0

            /// inainte de query trebuie sa faci un convert

            ea = eb = 0;

            for (j=0;j<p2;j++){
                for (k=1;k<=n;k++){
                    if (f[k] == a2[j])
                        ca[ea++] = k;
                }
            }

            for (j=0;j<q2;j++){
                for (k=1;k<=n;k++){
                    if (f[k] == b2[j])
                        cb[eb++] = k;
                }
            }


            if (i != 1 && query( ea , eb , ca , cb ) == 0){ /// ai pierdut
                for (j=0;j<p;j++){
                    a2[j] = a[j];
                }
                for (j=0;j<q;j++){
                    b2[j] = b[j];
                }
                p2 = p;
                q2 = q;
                /// in a le punem pe alea cu 0 , in b pe alea cu 1
                for (j = 0 ; j < p2 ; j++){
                    if ( (a2[j] & (1 << idk[i])) != 0 ){ /// asta are 1 , nu e ok
                        swap(a2[p2 - 1] , a2[j]);
                        p2--;
                        j--;
                    }
                }

                for (j = 0 ; j < q2 ; j++){
                    if ( (b2[j] & (1 << idk[i])) == 0 ){ /// asta are 0 , nu e ok
                        swap(b2[q2 - 1] , b2[j]);
                        q2--;
                        j--;
                    }
                }
                /// ai inversat ce era de inversat
            }

            /// e ok
            for (j=0;j<p2;j++){
                a[j] = a2[j];
            }
            for (j=0;j<q2;j++){
                b[j] = b2[j];
            }
            p = p2;
            q = q2;

        }

        /// in a si in b ai candidati la solutie
        /// cel putin partile cu biti diferiti
        /// in felul asta, eviti sa nu ai seturi disjuncte
        /// a si b sunt 2 multimi care au intersectia vida


        for (i = 1 ; i <= en ; i++){

            for (j=0;j<p;j++){
                a2[j] = a[j];
            }
            for (j=0;j<q;j++){
                b2[j] = b[j];
            }
            p2 = p;
            q2 = q;
            /// in a le punem pe alea cu 1 , in b pe alea cu 0
            for (j = 0 ; j < p2 ; j++){
                if ( (a2[j] & (1 << nope[i])) == 0 ){ /// asta are 0 , nu e ok
                    swap(a2[p2 - 1] , a2[j]);
                    p2--;
                    j--;
                }
            }

            for (j = 0 ; j < q2 ; j++){
                if ( (b2[j] & (1 << nope[i])) == 0 ){ /// asta are 0 , nu e ok
                    swap(b2[q2 - 1] , b2[j]);
                    q2--;
                    j--;
                }
            }
            /// in a2 ti au ramas cele cu configuratie fixata + 0
            /// in b2 ti au ramas cu configuratie fixata + 0


            ea = eb = 0;

            for (j=0;j<p2;j++){
                for (k=1;k<=n;k++){
                    if (f[k] == a2[j])
                        ca[ea++] = k;
                }
            }

            for (j=0;j<q2;j++){
                for (k=1;k<=n;k++){
                    if (f[k] == b2[j])
                        cb[eb++] = k;
                }
            }


            if (query( ea , eb , ca , cb ) == 0){ /// ai pierdut
                for (j=0;j<p;j++){
                    a2[j] = a[j];
                }
                for (j=0;j<q;j++){
                    b2[j] = b[j];
                }
                p2 = p;
                q2 = q;
                /// in a le punem pe alea cu 0 , in b pe alea cu 1
                for (j = 0 ; j < p2 ; j++){
                    if ( (a2[j] & (1 << nope[i])) != 0 ){ /// asta are 1 , nu e ok
                        swap(a2[p2 - 1] , a2[j]);
                        p2--;
                        j--;
                    }
                }

                for (j = 0 ; j < q2 ; j++){
                    if ( (b2[j] & (1 << nope[i])) != 0 ){ /// asta are 1 , nu e ok
                        swap(b2[q2 - 1] , b2[j]);
                        q2--;
                        j--;
                    }
                }
                /// ai inversat ce era de inversat
            }

            /// e ok
            for (j=0;j<p2;j++){
                a[j] = a2[j];
            }
            for (j=0;j<q2;j++){
                b[j] = b2[j];
            }
            p = p2;
            q = q2;

        }



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

        /// pt a

        ea = eb = 0;

        for (j=0;j<p;j++){
            for (k=1;k<=n;k++){
                if (f[k] == a[j])
                    ca[ea++] = k;
            }
        }

        for (j=0;j<q;j++){
            for (k=1;k<=n;k++){
                if (f[k] == b[j])
                    cb[eb++] = k;
            }
        }

        p = ea;
        q = eb;

        for (i=0;i<p;i++)
            a[i] = ca[i];


        for (i=0;i<q;i++)
            b[i] = cb[i];


        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 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 10 / 10