oj.uz

Submission #467547

# Submission time Handle Problem Language Result Execution time Memory
467547 2021-08-23T14:41:16 Z Bench0310 ICC (CEOI16_icc) C++17
100 / 100
 171 ms 588 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 460 KB Ok! 94 queries used.
2 Correct 7 ms 460 KB Ok! 97 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 460 KB Ok! 512 queries used.
2 Correct 40 ms 476 KB Ok! 519 queries used.
3 Correct 42 ms 488 KB Ok! 553 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 492 KB Ok! 1380 queries used.
2 Correct 136 ms 504 KB Ok! 1367 queries used.
3 Correct 142 ms 500 KB Ok! 1477 queries used.
4 Correct 142 ms 496 KB Ok! 1430 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 500 KB Ok! 1396 queries used.
2 Correct 140 ms 504 KB Ok! 1395 queries used.
3 Correct 135 ms 516 KB Ok! 1367 queries used.
4 Correct 140 ms 508 KB Ok! 1422 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 500 KB Ok! 1367 queries used.
2 Correct 136 ms 460 KB Ok! 1372 queries used.
3 Correct 137 ms 504 KB Ok! 1376 queries used.
4 Correct 171 ms 504 KB Ok! 1401 queries used.
5 Correct 139 ms 588 KB Ok! 1398 queries used.
6 Correct 136 ms 504 KB Ok! 1389 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 496 KB Ok! 1372 queries used.
2 Correct 136 ms 512 KB Ok! 1367 queries used.