Submission #467546

#	Time	Username	Problem	Language	Result	Execution time	Memory
467546		Bench0310	ICC (CEOI16_icc)	C++17	100 / 100	144 ms	612 KiB

icc

#include <bits/stdc++.h>
#include "icc.h"

using namespace std;
typedef long long ll;

//void setRoad(int a,int b)
//{
//    cout << "! " << a << " " << b << endl;
//}

int q(vector<int> a,vector<int> b)
{
    int sa=a.size();
    int sb=b.size();
    int x[sa];
    for(int i=0;i<sa;i++) x[i]=a[i];
    int y[sb];
    for(int i=0;i<sb;i++) y[i]=b[i];
//    cout << "? [ ";
//    for(int t:a) cout << t << " ";
//    cout << "] [ ";
//    for(int t:b) cout << t << " ";
//    cout << "]" << endl;
//    int r;
//    cin >> r;
//    return r;
    return query(sa,sb,x,y);
}

void run(int n)
{
    vector<vector<int>> v;
    for(int i=1;i<=n;i++) v.push_back({i});
    while(v.size()>1)
    {
        int cc=v.size();
        vector<int> id(n+1,-1);
        for(int i=0;i<cc;i++) for(int x:v[i]) id[x]=i;
        auto split=[&](int b)->array<vector<int>,2>
        {
            vector<int> one,two;
            for(int j=0;j<cc;j++)
            {
                if(j&(1<<b)) one.insert(one.end(),v[j].begin(),v[j].end());
                else two.insert(two.end(),v[j].begin(),v[j].end());
            }
            return {one,two};
        };
        int b=0;
        while(cc>>(b+1)) b++;
        for(int i=0;i<b;i++)
        {
            auto [one,two]=split(i);
            if(q(one,two)==1)
            {
                b=i;
                break;
            }
        }
        auto [one,two]=split(b);
        if(one.size()>two.size()) swap(one,two);
        auto go=[&](vector<int> x,vector<int> y)->int
        {
            int l=0,r=x.size();
            while(l<r-1)
            {
                int m=(l+r)/2;
                vector<int> tmp;
                for(int i=l;i<m;i++) tmp.push_back(x[i]);
                if(q(tmp,y)==1) r=m;
                else l=m;
            }
            return x[l];
        };
        int x=go(one,two);
        vector<int> now;
        for(int y:two)
        {
            bool opt=1;
            for(int i=0;i<b;i++) opt&=(((id[x]>>i)&1)==((id[y]>>i)&1));
            if(opt) now.push_back(y);
        }
        int y=go(now,{x});
        setRoad(x,y);
        vector<vector<int>> nxt;
        for(int i=0;i<cc;i++) if(i!=id[x]&&i!=id[y]) nxt.push_back(v[i]);
        vector<int> tmp=v[id[x]];
        tmp.insert(tmp.end(),v[id[y]].begin(),v[id[y]].end());
        nxt.push_back(tmp);
        v=nxt;
    }
}

//int main()
//{
//    ios::sync_with_stdio(0);
//    cin.tie(0);
//    run(5);
//    return 0;
//}

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 10 / 10