oj.uz

답안 #986064

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
986064 2024-05-19T17:12:53 Z alexdd CEOI16_icc (CEOI16_icc) C++17
18 / 100
 204 ms 852 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);
}
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];

        bool gasit=0;
        for(auto x:comps[tole])
        {
            for(auto y:comps[tori])
            {
                if(gasit)
                    continue;
                aska[0]=x;
                askb[0]=y;
                if(query(1,1,aska,askb))
                {
                    setRoad(x,y);
                    gasit=1;
                }
            }
        }
        if(!gasit)
        {
            while(1);
        }
        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:92:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         for(int i=0;i<ord.size();i++)
      |                     ~^~~~~~~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 604 KB Ok! 175 queries used.
2 Correct 7 ms 604 KB Ok! 180 queries used.

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 620 KB Ok! 1639 queries used.
2 Correct 75 ms 604 KB Ok! 1920 queries used.
3 Correct 74 ms 600 KB Ok! 1924 queries used.

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 204 ms 612 KB Number of queries more than 4500 out of 2250
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 185 ms 604 KB Number of queries more than 4000 out of 2000
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 171 ms 620 KB Number of queries more than 3550 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 161 ms 852 KB Number of queries more than 3250 out of 1625
2 Halted 0 ms 0 KB -