oj.uz

답안 #223527

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
223527 2020-04-15T10:50:16 Z MKopchev CEOI16_icc (CEOI16_icc) C++14
100 / 100
 172 ms 640 KB 
#include <bits/stdc++.h>
#include "icc.h"
using namespace std;

const int nmax=100+42;
/*
void setRoad(int a,int b)
{
    cout<<"set "<<a<<" "<<b<<endl;
}

int query(int size_a,int size_b,int a[],int b[])
{
    cout<<"size_a "<<size_a<<" a ";for(int i=0;i<size_a;i++)cout<<a[i]<<" ";cout<<endl;

    cout<<"size_b "<<size_b<<" b ";for(int i=0;i<size_b;i++)cout<<b[i]<<" ";cout<<endl;

    int ret;
    cin>>ret;
    return ret;
}
*/
int size_a,size_b,a[nmax],b[nmax];

int n;

int parent[nmax];

int root(int node)
{
    if(node==parent[node])return parent[node];
    parent[node]=root(parent[node]);
    return parent[node];
}

bool blocked[nmax][nmax];

int my_ask(vector<int> lhs,vector<int> rhs)
{
    bool direct=1;
    for(auto u:lhs)
        for(auto v:rhs)
            if(blocked[u][v]==0)direct=0;

    if(direct)return 0;

    size_a=lhs.size();
    for(int i=0;i<size_a;i++)
        a[i]=lhs[i];

    size_b=rhs.size();
    for(int i=0;i<size_b;i++)
        b[i]=rhs[i];

    return query(size_a,size_b,a,b);
}

vector<int> in[nmax];

void my_merge(int u,int v)
{
    setRoad(u,v);

    int le=root(u),ri=root(v);

    for(auto k:in[ri])
        in[le].push_back(k);

    in[ri]={};

    parent[ri]=le;
}

void my_reduce(vector<int> &to_reduce,vector<int> other)
{
    while(to_reduce.size()>1)
    {
        vector<int> help[2];
        help[0]={};
        help[1]={};

        for(int i=0;i<to_reduce.size();i++)
            help[i%2].push_back(to_reduce[i]);

        if(my_ask(help[0],other))to_reduce=help[0];
        else to_reduce=help[1];
    }
}
void run(int N)
{
    n=N;
    for(int i=1;i<=n;i++)parent[i]=i,in[i]={i};

    for(int road=1;road<n;road++)
    {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                blocked[i][j]=0;

        vector<int> lhs={};
        vector<int> rhs={};

        for(int bit=0;true;bit++)
        {
            lhs={};
            rhs={};

            for(int i=1;i<=n;i++)
                if((i&(1<<bit)))
                {
                    for(auto w:in[i])lhs.push_back(w);
                }
                else
                {
                    for(auto w:in[i])rhs.push_back(w);
                }

            if(lhs.size()==0||rhs.size()==0)continue;

            if(my_ask(lhs,rhs))break;

            else
            {
                for(auto u:lhs)
                    for(auto v:rhs)
                        blocked[u][v]=1;
            }
        }

        my_reduce(lhs,rhs);

        my_reduce(rhs,lhs);

        int u=lhs[0],v=rhs[0];

        my_merge(u,v);
    }
}
/*
int main()
{
    run(4);
}
*/

Compilation message

icc.cpp: In function 'void my_reduce(std::vector<int>&, std::vector<int>)':
icc.cpp:82:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<to_reduce.size();i++)
                     ~^~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 512 KB Ok! 102 queries used.
2 Correct 12 ms 640 KB Ok! 101 queries used.

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 512 KB Ok! 545 queries used.
2 Correct 59 ms 636 KB Ok! 651 queries used.
3 Correct 56 ms 512 KB Ok! 633 queries used.

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 140 ms 512 KB Ok! 1360 queries used.
2 Correct 170 ms 512 KB Ok! 1562 queries used.
3 Correct 146 ms 636 KB Ok! 1308 queries used.
4 Correct 160 ms 636 KB Ok! 1461 queries used.

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 145 ms 512 KB Ok! 1371 queries used.
2 Correct 153 ms 512 KB Ok! 1443 queries used.
3 Correct 159 ms 512 KB Ok! 1489 queries used.
4 Correct 159 ms 584 KB Ok! 1312 queries used.

Subtask #5
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 172 ms 512 KB Ok! 1542 queries used.
2 Correct 167 ms 632 KB Ok! 1499 queries used.
3 Correct 165 ms 632 KB Ok! 1514 queries used.
4 Correct 164 ms 512 KB Ok! 1473 queries used.
5 Correct 149 ms 512 KB Ok! 1408 queries used.
6 Correct 158 ms 512 KB Ok! 1472 queries used.

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 157 ms 512 KB Ok! 1503 queries used.
2 Correct 163 ms 512 KB Ok! 1555 queries used.