Submission #713416

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
713416	2023-03-22T01:28:38 Z	lam	ICC (CEOI16_icc)	C++14	Compilation error	0 ms	0 KB

icc

#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
typedef pair<int,int> ii;
#define ff first
#define ss second
const int maxn = 110;
vector<vector<int>> chan[maxn],le[maxn];
int n,m;
int p[maxn],s[maxn];
int get(int x)
{
    return p[x]=(p[x]==x)?x:get(p[x]);
}
void hop(int x, int y)
{
    x=get(x); y=get(y); if (x==y) return;
    if (s[x]>s[y]) swap(x,y);
    s[y]+=s[x];
    p[x]=y;
}
void dnc(int lx, int rx, vector <int> tmp, int level)
{
    if (lx==rx) return;
    random_shuffle(tmp.begin(),tmp.end());
    int mid=(lx+rx)/2;
    vector <int> tmp_chan, tmp_le;
    for (int i=lx; i<=rx; i++) if (i<=mid) tmp_le.push_back(tmp[i-lx]);
    else tmp_chan.push_back(tmp[i-lx]);
    le[level].push_back(tmp_le); chan[level].push_back(tmp_chan);
    dnc(lx,mid,tmp_le,level+1);
    dnc(mid+1,rx,tmp_chan,level+1);
}

ii trace(vector <int> tmp_le, vector <int> tmp_chan)
{
    if (tmp_chan.size() > tmp_le.size()) swap(tmp_le, tmp_chan);
    if (tmp_le.size()==tmp_chan.size()&&tmp_le.size()==1)
    {
        return {tmp_le[0], tmp_chan[0]};
    }
    int mid = (tmp_le.size() - 1)/2;
    random_shuffle(tmp_le.begin(),tmp_le.end());
    vector <int> tmp_le1, tmp_le2;
    for (int i=0; i<tmp_le.size(); i++) if (i<=mid) tmp_le1.push_back(tmp_le[i]);
    else tmp_le2.push_back(tmp_le[i]);
    bool has = query(tmp_le1.size(),tmp_chan.size(),tmp_le1,tmp_chan);
    if (has) return trace(tmp_le1,tmp_chan);
    else return trace(tmp_le2,tmp_chan);
}

void run(int N)
{
    n=N;
    for (int i=1; i<=n; i++) p[i]=i, s[i]=1;
    for (int it=1; it<=n-1; it++)
    {
        vector <int> tmp;
        for (int i=1; i<=n; i++) if (p[i]==i) tmp.push_back(i), chan[i].clear(), le[i].clear();
        m=tmp.size();
        dnc(1,m,tmp,1);
        int level = 1;
        while (true)
        {
            vector <int> tmp_le, tmp_chan;
            for (vector <int> i:le[level]) for (int j:i) tmp_le.push_back(j);
            for (vector <int> i:chan[level]) for (int j:i) tmp_chan.push_back(j);
            bool has = query(tmp_le.size(),tmp_chan.size(),le,chan);
            if (has==1) break;
        }
        int l=0; int r=le[level].size()-1;
        int ans=-1;
        while (l<=r)
        {
            int mid=(l+r)/2;
            vector <int> tmp_le, tmp_chan;
            for (int i=mid; i<le[level].size(); i++)
                for (int j:le[level][i]) tmp_le.push_back(j);
            for (int i=mid; i<chan[level].size(); i++)
                for (int j:chan[level][i]) tmp_chan.push_back(j);
            bool has = query(tmp_le.size(),tmp_chan.size(),le,chan);
            if (has)
            {
                ans = mid;
                l=mid+1;
            }
            else r=mid-1;
        }
        ii canh = trace(le[level][ans],chan[level][ans]);
        setRoad(canh.ff, canh.ss);
        hop(canh.ff,canh.ss);
    }
}

Compilation message

icc.cpp: In function 'ii trace(std::vector<int>, std::vector<int>)':
icc.cpp:45:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for (int i=0; i<tmp_le.size(); i++) if (i<=mid) tmp_le1.push_back(tmp_le[i]);
      |                   ~^~~~~~~~~~~~~~
icc.cpp:47:53: error: cannot convert 'std::vector<int>' to 'int*'
   47 |     bool has = query(tmp_le1.size(),tmp_chan.size(),tmp_le1,tmp_chan);
      |                                                     ^~~~~~~
      |                                                     |
      |                                                     std::vector<int>
In file included from icc.cpp:2:
icc.h:10:30: note:   initializing argument 3 of 'int query(int, int, int*, int*)'
   10 | int query(int a, int b, int *A, int *B);
      |                         ~~~~~^
icc.cpp: In function 'void run(int)':
icc.cpp:68:60: error: cannot convert 'std::vector<std::vector<int> >*' to 'int*'
   68 |             bool has = query(tmp_le.size(),tmp_chan.size(),le,chan);
      |                                                            ^~
      |                                                            |
      |                                                            std::vector<std::vector<int> >*
In file included from icc.cpp:2:
icc.h:10:30: note:   initializing argument 3 of 'int query(int, int, int*, int*)'
   10 | int query(int a, int b, int *A, int *B);
      |                         ~~~~~^
icc.cpp:77:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |             for (int i=mid; i<le[level].size(); i++)
      |                             ~^~~~~~~~~~~~~~~~~
icc.cpp:79:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |             for (int i=mid; i<chan[level].size(); i++)
      |                             ~^~~~~~~~~~~~~~~~~~~
icc.cpp:81:60: error: cannot convert 'std::vector<std::vector<int> >*' to 'int*'
   81 |             bool has = query(tmp_le.size(),tmp_chan.size(),le,chan);
      |                                                            ^~
      |                                                            |
      |                                                            std::vector<std::vector<int> >*
In file included from icc.cpp:2:
icc.h:10:30: note:   initializing argument 3 of 'int query(int, int, int*, int*)'
   10 | int query(int a, int b, int *A, int *B);
      |                         ~~~~~^