Submission #986014

#	Time	Username	Problem	Language	Result	Execution time	Memory
986014		alexdd	ICC (CEOI16_icc)	C++17	0 / 100	192 ms	640 KiB

icc

#include "icc.h"
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n;
vector<int> comps[105];
vector<int> ord;
int aska[105],askb[105],sa,sb;
int wirtz(int poz)
{
    sa=sb=0;
    for(int i=0;i<=poz;i++)
        for(auto x:comps[ord[i]])
            aska[sa++]=x;
    for(int i=poz+1;i<ord.size();i++)
        for(auto x:comps[ord[i]])
            askb[sb++]=x;
    return query(sa,sb,aska,askb);
}
void run(int N)
{
    n=N;
    for(int i=1;i<=n;i++)
    {
        ord.push_back(i);
        comps[i].push_back(i);
    }
    for(int pas=1;pas<n;pas++)
    {
       // cout<<pas<<" pas incepe\n";
        do
        {
            random_shuffle(ord.begin(),ord.end());
        }while(!wirtz((int)ord.size()/2-1));
       // cout<<pas<<" pas intermediar\n";
        int st,dr,ans;
        st=0;
        dr=(int)ord.size()/2-2;
        ans=(int)ord.size()/2-1;
        while(st<=dr)
        {
            int mij=(st+dr)/2;
            if(wirtz(mij))
            {
                ans=mij;
                dr=mij-1;
            }
            else
                st=mij+1;
        }
        int tole = ord[ans];
        st=(int)ord.size()/2;
        dr=(int)ord.size()-1;
        ans=(int)ord.size()/2-1;
        while(st<=dr)
        {
            int mij=(st+dr)/2;
            if(wirtz(mij))
            {
                ans=mij;
                st=mij+1;
            }
            else
                dr=mij-1;
        }
        int tori = ord[ans+1];

        for(auto x:comps[tole])
        {
            for(auto y:comps[tori])
            {
                aska[0]=x;
                askb[0]=y;
                if(query(1,1,aska,askb))
                {
                    setRoad(x,y);
                }
            }
        }

        for(auto x:comps[tori])
            comps[tole].push_back(x);
        comps[tori].clear();
        for(int i=0;i<ord.size();i++)
        {
            if(ord[i]==tori)
            {
                ord.erase(ord.begin()+i);
                break;
            }
        }
    }
}
/**

4
1 2
1 3
3 4

*/

Compilation message (stderr)

icc.cpp: In function 'int wirtz(int)':
icc.cpp:16:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for(int i=poz+1;i<ord.size();i++)
      |                     ~^~~~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:85:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         for(int i=0;i<ord.size();i++)
      |                     ~^~~~~~~~~~~

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