Submission #720291

#	Time	Username	Problem	Language	Result	Execution time	Memory
720291		groshi	ICC (CEOI16_icc)	C++17	100 / 100	126 ms	628 KiB

icc

#include<bits/stdc++.h>
#include "icc.h"
using namespace std;
int przewodnik[200];
vector<int> spojne[200];
vector<int> mam;
int n;
int aaa[200],bbb[200];
int Query(int a1,int b1,vector<int> a,vector<int> b)
{
    for(int i=0;i<a1;i++)
        aaa[i]=a[i];
    for(int i=0;i<b1;i++)
        bbb[i]=b[i];
    return query(a1,b1,aaa,bbb);
}
void dodaj(int x,int y)
{
    setRoad(x,y);
    x=przewodnik[x];
    y=przewodnik[y];
    for(int i=0;i<spojne[x].size();i++)
        spojne[y].push_back(spojne[x][i]),przewodnik[spojne[x][i]]=y;
    spojne[x].clear();
    mam.clear();
    for(int i=1;i<=n;i++)
        if(spojne[i].size())
            mam.push_back(i);
}
void pytaj(vector<pair<int,int>> przedzialy)
{
    vector<int> a[2];
    for(int i=0;i<przedzialy.size();i++)
        for(int j=przedzialy[i].first;j<=przedzialy[i].second;j++)
            for(int b=0;b<spojne[mam[j]].size();b++)
                a[i%2].push_back(spojne[mam[j]][b]);
    int co=Query(a[0].size(),a[1].size(),a[0],a[1]);
    if(co==0)
    {
        vector<pair<int,int> > jazda;
        for(int i=0;i<przedzialy.size();i++)
        {
            if(przedzialy[i].first==przedzialy[i].second)
                continue;
            jazda.push_back({przedzialy[i].first,(przedzialy[i].first+przedzialy[i].second)/2});
            jazda.push_back({(przedzialy[i].first+przedzialy[i].second)/2+1,przedzialy[i].second});
        }
        pytaj(jazda);
        return;
    }
    int pocz=0,kon=a[0].size(),sre,ostd;
    while(pocz<kon)
    {
        sre=(pocz+kon)/2;
        vector<int> pytanko;
        for(int i=pocz;i<=sre;i++)
            pytanko.push_back(a[0][i]);
        int co=Query(pytanko.size(),a[1].size(),pytanko,a[1]);
        if(co)
        {
            ostd=sre;
            kon=sre;
        }
        else pocz=sre+1;
    }
    int pocz1=0,kon1=a[1].size(),sre1,ostd1;
    while(pocz1<kon1)
    {
        sre1=(pocz1+kon1)/2;
        vector<int> pytanko;
        for(int i=pocz1;i<=sre1;i++)
            pytanko.push_back(a[1][i]);
        int co=Query(pytanko.size(),a[0].size(),pytanko,a[0]);
        if(co)
        {
            ostd1=sre1;
            kon1=sre1;
        }
        else pocz1=sre1+1;
    }
    dodaj(a[0][ostd],a[1][ostd1]);
    return;
}
void run(int N)
{
    n=N;
    for(int i=1;i<=n;i++)
        spojne[i].push_back(i),mam.push_back(i),przewodnik[i]=i;
    for(int i=1;i<n;i++)
    {
        vector<pair<int,int> > przedzialy;
        przedzialy.push_back({0,mam.size()/2-1});
        przedzialy.push_back({mam.size()/2,mam.size()-1});
        pytaj(przedzialy);
    }
}

Compilation message (stderr)

icc.cpp: In function 'void dodaj(int, int)':
icc.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int i=0;i<spojne[x].size();i++)
      |                 ~^~~~~~~~~~~~~~~~~
icc.cpp: In function 'void pytaj(std::vector<std::pair<int, int> >)':
icc.cpp:33:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for(int i=0;i<przedzialy.size();i++)
      |                 ~^~~~~~~~~~~~~~~~~~
icc.cpp:35:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |             for(int b=0;b<spojne[mam[j]].size();b++)
      |                         ~^~~~~~~~~~~~~~~~~~~~~~
icc.cpp:41:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for(int i=0;i<przedzialy.size();i++)
      |                     ~^~~~~~~~~~~~~~~~~~
icc.cpp:81:32: warning: 'ostd1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   81 |     dodaj(a[0][ostd],a[1][ostd1]);
      |                                ^
icc.cpp:81:20: warning: 'ostd' may be used uninitialized in this function [-Wmaybe-uninitialized]
   81 |     dodaj(a[0][ostd],a[1][ostd1]);
      |                    ^

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