Submission #231106

#	Time	Username	Problem	Language	Result	Execution time	Memory
231106		nicolaalexandra	ICC (CEOI16_icc)	C++14	100 / 100	165 ms	640 KiB

icc

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

int n;
int v[DIM],t[DIM],aux[DIM],a[DIM],b[DIM],f[10],poz[DIM];

/*int query (int n, int m, int a[], int b[]){
    int ans;
    cout<<n<<" ";
    for (int i=0;i<n;i++)
        cout<<a[i]<<" ";
    cout<<endl;
    cout<<m<<" ";
    for (int i=0;i<m;i++)
        cout<<b[i]<<" ";
    cout<<endl;
    cin>>ans;
    return ans;
}
void setRoad (int x, int y){
    cout<<x<<" "<<y<<endl;
}*/

int get_rad (int x){
    while (t[x] > 0)
        x = t[x];
    return x;
}
void _union (int x, int y){
    int radx = get_rad (x), rady = get_rad (y);

    if (t[radx] < t[rady]){
        t[radx] += t[rady];
        t[rady] = radx;
    } else {
        t[rady] += t[radx];
        t[radx] = rady;
    }

}

void run (int n){
    int k,k2,el,i,x,y,nr_comp=n;
    for (i=1;i<=n;i++)
        t[i] = -1;
    memset (f,0,sizeof f);
    for (int pas=1;pas<n;pas++){
        /// impart componentele conexe in doua multimi

        memset (poz,0,sizeof poz);
        int idk = 0;
        for (i=1;i<=n;i++){
            int val = get_rad(i);
            if (t[i] < 0) /// radacina
                poz[i] = ++idk;
        }


        for (int bit=0;(1<<bit)<=nr_comp;bit++){
            k = 0, k2 = 0;

            for (i=1;i<=n;i++){
                int val = poz[get_rad(i)];
                if (val&(1<<bit))
                    a[k++] = i;
                else b[k2++] = i;
            }

           // if (!k || !k2)
              //  continue;

            if (query(k,k2,a,b))
                f[bit] = 1; /// stiu clar ca aici sunt bitii diferiti
            else f[bit] = 0;
        }

        /// acum iau un bit random care stiu ca are rezultatul 1
        int comp1 = 0, comp2 = 0, bit2;
        for (int bit=0;(1<<bit)<=nr_comp;bit++){
            if (f[bit]){
                comp2 += (1<<bit);
                bit2 = bit;
                break;
            }}

        for (int bit=0;(1<<bit)<=nr_comp;bit++){
            if (bit == bit2)
                continue;

            if (!f[bit]){ /// ambii biti sunt 1 sau 0
                k = 0, k2 = 0;
                for (i=1;i<=n;i++){
                    int val = poz[get_rad(i)];
                    if (!(val&(1<<bit2)) && !(val&(1<<bit)))
                        a[k++] = i;
                    if ((val&(1<<bit2)) && !(val&(1<<bit)))
                        b[k2++] = i;
                }
                if (!query (k,k2,a,b)){
                    comp1 += (1<<bit);
                    comp2 += (1<<bit);
                }
            } else { /// trebuie sa vad care e 1 si care e 0
                k = 0, k2 = 0;
                for (i=1;i<=n;i++){
                    int val = poz[get_rad(i)];
                    if (!(val&(1<<bit2)) && !(val&(1<<bit)))
                        a[k++] = i;
                    if ((val&(1<<bit2)) && (val&(1<<bit)))
                        b[k2++] = i;
                }
                if (query(k,k2,a,b))
                    comp2 += (1<<bit);
                else comp1 += (1<<bit);
            }
        }


        /// acum determinam x si y din cele doua componente
        k = 0, k2 = 0;
        for (i=1;i<=n;i++){
            int val = poz[get_rad(i)];
            if (val == comp1)
                a[k++] = i;
            if (val == comp2)
                b[k2++] = i;
        }

        while (k > 1){
            int mid = k/2;

            if (query(mid,k2,a,b))
                k = mid;
            else {
                for (int i=mid;i<k;i++)
                    a[i-mid] = a[i];
                k -= mid;
            }
        }
        x = a[0];


        while (k2 > 1){
            int mid = k2/2;

            if (query(k,mid,a,b))
                k2 = mid;
            else {
                for (int i=mid;i<k2;i++)
                    b[i-mid] = b[i];
                k2 -= mid;
            }
        }
        y = b[0];

        setRoad(x,y);

        _union (x,y);
        nr_comp--;
    }
}

Compilation message (stderr)

icc.cpp: In function 'void run(int)':
icc.cpp:56:17: warning: unused variable 'val' [-Wunused-variable]
             int val = get_rad(i);
                 ^~~
icc.cpp:46:14: warning: unused variable 'el' [-Wunused-variable]
     int k,k2,el,i,x,y,nr_comp=n;
              ^~
icc.cpp:90:13: warning: 'bit2' may be used uninitialized in this function [-Wmaybe-uninitialized]
             if (bit == bit2)
             ^~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 10 / 10