Submission #58421

#	Time	Username	Problem	Language	Result	Execution time	Memory
58421		MatheusLealV	ICC (CEOI16_icc)	C++17	90 / 100	204 ms	852 KiB

icc

#include "icc.h"
#define N 105
#define f first
#define s second
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

set<int> grafo[N];

int pai[N], peso[N], ni;

vector<int> el[N];

int Find(int x)
{
    if(x == pai[x]) return x;

    return pai[x] = Find(pai[x]);
}

void join(int a, int b)
{
    a = Find(a), b = Find(b);

    if(a == b) return;

    if(peso[a] > peso[b])
    {
        pai[b] = a;

        for(auto x: el[b]) el[a].push_back(x);
    }

    else if(peso[a] <= peso[b])
    {
        pai[a] = b;

        for(auto x: el[a]) el[b].push_back(x);

        if(peso[a] == peso[b]) peso[b] ++;
    }
}

pii Find_Pair(vector<int> esq, vector<int> dir)
{

    int ini = 0, fim = dir.size() - 2, mid, best1 = dir.size() - 1, best2 = esq.size() - 1;

    int A[N], idl = 0, aux[N], idaux = 0;

    for(int i = 0; i < esq.size(); i++) A[idl] = esq[i], idl ++;

    for(int i = 0; i < dir.size(); i++) aux[i] = dir[i];

    if(!query((int)esq.size(), (int) dir.size(), A, aux)) return {-1, -1}; 

    while(fim >= ini)
    {
        mid = (ini + fim)/2;

        int B[N], idr = 0;

        for(int i = 0; i <= mid; i++) B[idr] = dir[i], idr ++;

        if(query(idl, idr, A, B))
        {
            best1 = mid;

            fim = mid - 1;
        }

        else ini = mid + 1;
    }

    ini = 0, fim = esq.size() - 2, mid;

    idl = 0;

    for(int i = 0; i < dir.size(); i++) A[idl] = dir[i], idl ++;

    while(fim >= ini)
    {
        mid = (ini + fim)/2;

        int B[N], idr = 0;

        for(int i = 0; i <= mid; i++) B[idr] = esq[i], idr ++;

        if(query(idl, idr, A, B))
        {
            best2 = mid;

            fim = mid - 1;
        }

        else ini = mid + 1;
    }

    //cout<<"ACHEI "<<best1<<" "<<best2<<"\n";

    if(best1 == -1 and best2 == -1) return {-1, -1};

    return {dir[best1], esq[best2]};
}

void run(int n)
{
    ni = n;

    for(int i = 1; i <= n; i++) pai[i] = i, el[i].push_back(i);

    for(int i = 1; i < n; i++)
    {
        set<int> aux; vector<int> val;

        for(int i = 1; i <= n; i++) aux.insert(Find(i));

        for(auto x: aux) val.push_back(x);

        vector<int> bits;

        for(int k = 0; k < 7; k++)
        {
            vector<int> esq, dir;

            for(int i = 0; i < val.size(); i++)
            {
                if(i & (1<<k))
                {
                    int x = val[i];

                    for(auto v: el[x]) esq.push_back(v);
                }

                else
                {
                    int x = val[i];

                    for(auto v: el[x]) dir.push_back(v);
                }
            }

            pii P = Find_Pair(esq, dir);

            if(P.f != -1 and P.s != -1)
            {
                setRoad(P.f, P.s);

                join(P.f, P.s);

                break;
            }
        }
    }
}

Compilation message (stderr)

icc.cpp:4:11: warning: literal operator suffixes not preceded by '_' are reserved for future standardization [-Wliteral-suffix]
 #define s second
           ^
icc.cpp:4:11: warning: literal operator suffixes not preceded by '_' are reserved for future standardization [-Wliteral-suffix]
 #define s second
           ^
icc.cpp:4:11: warning: literal operator suffixes not preceded by '_' are reserved for future standardization [-Wliteral-suffix]
 #define s second
           ^
icc.cpp:4:11: warning: literal operator suffixes not preceded by '_' are reserved for future standardization [-Wliteral-suffix]
 #define s second
           ^
icc.cpp:4:11: warning: literal operator suffixes not preceded by '_' are reserved for future standardization [-Wliteral-suffix]
 #define s second
           ^
icc.cpp:4:11: warning: literal operator suffixes not preceded by '_' are reserved for future standardization [-Wliteral-suffix]
 #define s second
           ^
icc.cpp: In function 'pii Find_Pair(std::vector<int>, std::vector<int>)':
icc.cpp:52:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < esq.size(); i++) A[idl] = esq[i], idl ++;
                    ~~^~~~~~~~~~~~
icc.cpp:54:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < dir.size(); i++) aux[i] = dir[i];
                    ~~^~~~~~~~~~~~
icc.cpp:76:39: warning: right operand of comma operator has no effect [-Wunused-value]
     ini = 0, fim = esq.size() - 2, mid;
                                       ^
icc.cpp:80:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < dir.size(); i++) A[idl] = dir[i], idl ++;
                    ~~^~~~~~~~~~~~
icc.cpp:50:32: warning: unused variable 'idaux' [-Wunused-variable]
     int A[N], idl = 0, aux[N], idaux = 0;
                                ^~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:127:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < val.size(); i++)
                            ~~^~~~~~~~~~~~

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