oj.uz

Submission #986014

# Submission time Handle Problem Language Result Execution time Memory
986014 2024-05-19T16:03:26 Z alexdd ICC (CEOI16_icc) C++17
0 / 100
 192 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);
}
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

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.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 604 KB Ok! 177 queries used.
2 Incorrect 1 ms 604 KB Wrong road!
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 640 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 604 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 604 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 640 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 192 ms 624 KB Number of queries more than 3250 out of 1625
2 Halted 0 ms 0 KB -