oj.uz

Submission #720291

# Submission time Handle Problem Language Result Execution time Memory
720291 2023-04-07T21:14:45 Z groshi ICC (CEOI16_icc) C++17
100 / 100
 126 ms 628 KB 
#include<bits/stdc++.h>
#include "icc.h"
using namespace std;
int przewodnik[200];
vector<int> spojne[200];
vector<int> mam;
int n;
int aaa[200],bbb[200];
int Query(int a1,int b1,vector<int> a,vector<int> b)
{
    for(int i=0;i<a1;i++)
        aaa[i]=a[i];
    for(int i=0;i<b1;i++)
        bbb[i]=b[i];
    return query(a1,b1,aaa,bbb);
}
void dodaj(int x,int y)
{
    setRoad(x,y);
    x=przewodnik[x];
    y=przewodnik[y];
    for(int i=0;i<spojne[x].size();i++)
        spojne[y].push_back(spojne[x][i]),przewodnik[spojne[x][i]]=y;
    spojne[x].clear();
    mam.clear();
    for(int i=1;i<=n;i++)
        if(spojne[i].size())
            mam.push_back(i);
}
void pytaj(vector<pair<int,int>> przedzialy)
{
    vector<int> a[2];
    for(int i=0;i<przedzialy.size();i++)
        for(int j=przedzialy[i].first;j<=przedzialy[i].second;j++)
            for(int b=0;b<spojne[mam[j]].size();b++)
                a[i%2].push_back(spojne[mam[j]][b]);
    int co=Query(a[0].size(),a[1].size(),a[0],a[1]);
    if(co==0)
    {
        vector<pair<int,int> > jazda;
        for(int i=0;i<przedzialy.size();i++)
        {
            if(przedzialy[i].first==przedzialy[i].second)
                continue;
            jazda.push_back({przedzialy[i].first,(przedzialy[i].first+przedzialy[i].second)/2});
            jazda.push_back({(przedzialy[i].first+przedzialy[i].second)/2+1,przedzialy[i].second});
        }
        pytaj(jazda);
        return;
    }
    int pocz=0,kon=a[0].size(),sre,ostd;
    while(pocz<kon)
    {
        sre=(pocz+kon)/2;
        vector<int> pytanko;
        for(int i=pocz;i<=sre;i++)
            pytanko.push_back(a[0][i]);
        int co=Query(pytanko.size(),a[1].size(),pytanko,a[1]);
        if(co)
        {
            ostd=sre;
            kon=sre;
        }
        else pocz=sre+1;
    }
    int pocz1=0,kon1=a[1].size(),sre1,ostd1;
    while(pocz1<kon1)
    {
        sre1=(pocz1+kon1)/2;
        vector<int> pytanko;
        for(int i=pocz1;i<=sre1;i++)
            pytanko.push_back(a[1][i]);
        int co=Query(pytanko.size(),a[0].size(),pytanko,a[0]);
        if(co)
        {
            ostd1=sre1;
            kon1=sre1;
        }
        else pocz1=sre1+1;
    }
    dodaj(a[0][ostd],a[1][ostd1]);
    return;
}
void run(int N)
{
    n=N;
    for(int i=1;i<=n;i++)
        spojne[i].push_back(i),mam.push_back(i),przewodnik[i]=i;
    for(int i=1;i<n;i++)
    {
        vector<pair<int,int> > przedzialy;
        przedzialy.push_back({0,mam.size()/2-1});
        przedzialy.push_back({mam.size()/2,mam.size()-1});
        pytaj(przedzialy);
    }
}

Compilation message

icc.cpp: In function 'void dodaj(int, int)':
icc.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int i=0;i<spojne[x].size();i++)
      |                 ~^~~~~~~~~~~~~~~~~
icc.cpp: In function 'void pytaj(std::vector<std::pair<int, int> >)':
icc.cpp:33:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for(int i=0;i<przedzialy.size();i++)
      |                 ~^~~~~~~~~~~~~~~~~~
icc.cpp:35:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |             for(int b=0;b<spojne[mam[j]].size();b++)
      |                         ~^~~~~~~~~~~~~~~~~~~~~~
icc.cpp:41:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for(int i=0;i<przedzialy.size();i++)
      |                     ~^~~~~~~~~~~~~~~~~~
icc.cpp:81:32: warning: 'ostd1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   81 |     dodaj(a[0][ostd],a[1][ostd1]);
      |                                ^
icc.cpp:81:20: warning: 'ostd' may be used uninitialized in this function [-Wmaybe-uninitialized]
   81 |     dodaj(a[0][ostd],a[1][ostd1]);
      |                    ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Ok! 106 queries used.
2 Correct 6 ms 500 KB Ok! 106 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 468 KB Ok! 532 queries used.
2 Correct 28 ms 496 KB Ok! 586 queries used.
3 Correct 31 ms 432 KB Ok! 631 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 508 KB Ok! 1459 queries used.
2 Correct 98 ms 524 KB Ok! 1384 queries used.
3 Correct 114 ms 504 KB Ok! 1600 queries used.
4 Correct 98 ms 468 KB Ok! 1514 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 516 KB Ok! 1543 queries used.
2 Correct 103 ms 512 KB Ok! 1546 queries used.
3 Correct 100 ms 528 KB Ok! 1548 queries used.
4 Correct 98 ms 516 KB Ok! 1529 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 508 KB Ok! 1549 queries used.
2 Correct 107 ms 512 KB Ok! 1548 queries used.
3 Correct 96 ms 524 KB Ok! 1548 queries used.
4 Correct 99 ms 512 KB Ok! 1559 queries used.
5 Correct 126 ms 468 KB Ok! 1506 queries used.
6 Correct 97 ms 628 KB Ok! 1543 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 520 KB Ok! 1571 queries used.
2 Correct 100 ms 524 KB Ok! 1547 queries used.