Submission #986067

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
986067	2024-05-19T17:21:44 Z	alexdd	ICC (CEOI16_icc)	C++17	40 / 100	116 ms	640 KB

#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);
}
int boniface(int c1, int poz1, int c2)
{
    sa=sb=0;
    for(int i=0;i<=poz1;i++)
        aska[sa++]=comps[c1][i];
    for(auto x:comps[c2])
        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()-2;
        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];

        st=0;
        dr=(int)comps[tole].size()-2;
        ans=(int)comps[tole].size()-1;
        while(st<=dr)
        {
            int mij=(st+dr)/2;
            if(boniface(tole,mij,tori))
            {
                ans=mij;
                dr=mij-1;
            }
            else
                st=mij+1;
        }
        int v1 = comps[tole][ans];
        st=0;
        dr=(int)comps[tori].size()-2;
        ans=(int)comps[tori].size()-1;
        while(st<=dr)
        {
            int mij=(st+dr)/2;
            if(boniface(tori,mij,tole))
            {
                ans=mij;
                dr=mij-1;
            }
            else
                st=mij+1;
        }
        int v2 = comps[tori][ans];

        setRoad(v1,v2);

        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

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:114:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |         for(int i=0;i<ord.size();i++)
      |                     ~^~~~~~~~~~~

Subtask #1
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	604 KB	Ok! 113 queries used.
2	Correct	5 ms	604 KB	Ok! 118 queries used.

Subtask #2
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	600 KB	Ok! 670 queries used.
2	Correct	35 ms	640 KB	Ok! 854 queries used.
3	Correct	37 ms	640 KB	Ok! 841 queries used.

Subtask #3
22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	96 ms	628 KB	Ok! 1830 queries used.
2	Correct	116 ms	620 KB	Ok! 2136 queries used.
3	Correct	112 ms	624 KB	Ok! 2050 queries used.
4	Correct	104 ms	620 KB	Ok! 2012 queries used.