답안 #986068

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
986068	2024-05-19T17:22:34 Z	alexdd	CEOI16_icc (CEOI16_icc)	C++17	40 / 100	111 ms	632 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();
        random_shuffle(comps[tole].begin(),comps[tole].end());
        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:115:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |         for(int i=0;i<ord.size();i++)
      |                     ~^~~~~~~~~~~

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	600 KB	Ok! 112 queries used.
2	Correct	4 ms	600 KB	Ok! 114 queries used.

Subtask #2
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	600 KB	Ok! 672 queries used.
2	Correct	37 ms	604 KB	Ok! 862 queries used.
3	Correct	34 ms	600 KB	Ok! 855 queries used.

Subtask #3
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	94 ms	600 KB	Ok! 1875 queries used.
2	Correct	111 ms	600 KB	Ok! 2083 queries used.
3	Correct	102 ms	628 KB	Ok! 2050 queries used.
4	Correct	103 ms	604 KB	Ok! 1976 queries used.