oj.uz

Submission #725067

# Submission time Handle Problem Language Result Execution time Memory
725067 2023-04-16T17:44:06 Z FatihSolak ICC (CEOI16_icc) C++17
100 / 100
 130 ms 796 KB 
#include <bits/stdc++.h>
#include "icc.h"
#define N 105
using namespace std;
vector<int> adj[N];
vector<int> x;
bool vis[N];
int qu = 1625;
void dfs(int v){
    vis[v] = 1;
    x.push_back(v);
    for(auto u:adj[v]){
        if(!vis[u]){
            dfs(u);
        }
    }
}
/*
void setRoad(int a,int b){
    cout <<"ROAD: " <<  a << " " << b << endl;
    return;
}
int query(int sa,int sb,int a[],int b[]){
    for(int i=0;i<sa;i++){
        cout << a[i] << " ";
    }
    cout << endl;
    for(int i=0;i<sb;i++){
        cout << b[i] << " ";
    }
    cout << endl;
    int ret;
    cin >> ret;
    return ret;
}*/
void solve2(vector<int> l,vector<int> r){
    if(l.size() == 1 && r.size() == 1){
        setRoad(l[0],r[0]);
        adj[l[0]].push_back(r[0]);
        adj[r[0]].push_back(l[0]);
        return;
    }
    if(l.size() == 1){
        vector<int> a,b;
        for(int i=0;i<(int)(r.size()+1)/2;i++){
            a.push_back(r[i]);
        }
        for(int i=(r.size()+1)/2;i<(int)r.size();i++){
            b.push_back(r[i]);
        }
        int sum1 = 1,sum2 = a.size();
        int al[sum1],ar[sum2];
        al[0] = l[0];
        for(int i = 0;i<(int)sum2;i++){
            ar[i] = a[i];
        }
        qu--;
        assert(qu >= 0);
        if(query(sum1,sum2,al,ar)){
            solve2(l,a);
        }
        else solve2(l,b);
    }
    else{
        vector<int> a,b;
        for(int i=0;i<(int)(l.size()+1)/2;i++){
            a.push_back(l[i]);
        }
        for(int i=(l.size()+1)/2;i<(int)l.size();i++){
            b.push_back(l[i]);
        }
        int sum1 = a.size(),sum2 = r.size();
        int al[sum1],ar[sum2];
        for(int i = 0;i<(int)sum1;i++){
            al[i] = a[i];
        }
        for(int i = 0;i<(int)sum2;i++){
            ar[i] = r[i];
        }
        qu--;
        assert(qu >= 0);
        if(query(sum1,sum2,al,ar)){
            solve2(a,r);
        }
        else solve2(b,r);
    }
}
void go(vector<vector<vector<int>>> a,vector<vector<vector<int>>> b){
     vector<int> l,r;
    for(auto u:a){
        for(auto c:u){
            for(auto d:c)
                l.push_back(d);
        }
    }
    for(auto u:b){
        for(auto c:u){
            for(auto d:c)
                r.push_back(d);
        }
    }
    solve2(l,r);
}
void solve(vector<vector<int>> tmp){
    vector<vector<vector<int>>> v;
    v.push_back(tmp);
    while(1){
        vector<vector<vector<int>>> a,b;
        int sum1 = 0;
        int sum2 = 0;
        for(auto comps:v){
            vector<vector<int>> l,r;
            for(int i=0;i<(int)comps.size()/2;i++){
                l.push_back(comps[i]);
                sum1 += comps[i].size();
            }
            for(int i=comps.size()/2;i<(int)comps.size();i++){
                r.push_back(comps[i]);
                sum2 += comps[i].size();
            }
            a.push_back(l);
            b.push_back(r);
        }
        int l[sum1],r[sum2];
        int cnt = 0;
        for(auto u:a){
            for(auto c:u){
                for(auto d:c){
                    l[cnt++] = d;
                }
            }
        }
        cnt = 0;
        for(auto u:b){
            for(auto c:u){
                for(auto d:c){
                    r[cnt++] = d;
                }
            }
        }
 
        qu--;
        assert(qu >= 0);
        if(query(sum1,sum2,l,r)){
            go(a,b);
            return;
        }
        v = a;
        for(auto u:b)v.push_back(u);
    }
}
void run(int n){
    srand(time(NULL));
    for(int i = 1;i<n;i++){
        vector<vector<int>> comps;
        for(int j=1;j<=n;j++){
            vis[j] = 0;
        }
        for(int j=1;j<=n;j++){
            if(!vis[j]){
                x.clear();
                dfs(j);
                comps.push_back(x);
            }
        }
        random_shuffle(comps.begin(),comps.end());
        solve(comps);
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 468 KB Ok! 105 queries used.
2 Correct 5 ms 468 KB Ok! 96 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 588 KB Ok! 528 queries used.
2 Correct 35 ms 708 KB Ok! 634 queries used.
3 Correct 35 ms 588 KB Ok! 637 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 756 KB Ok! 1433 queries used.
2 Correct 128 ms 600 KB Ok! 1585 queries used.
3 Correct 118 ms 580 KB Ok! 1615 queries used.
4 Correct 117 ms 588 KB Ok! 1484 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 576 KB Ok! 1449 queries used.
2 Correct 109 ms 596 KB Ok! 1469 queries used.
3 Correct 123 ms 636 KB Ok! 1606 queries used.
4 Correct 106 ms 628 KB Ok! 1443 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 588 KB Ok! 1580 queries used.
2 Correct 125 ms 768 KB Ok! 1597 queries used.
3 Correct 127 ms 568 KB Ok! 1612 queries used.
4 Correct 118 ms 636 KB Ok! 1579 queries used.
5 Correct 115 ms 796 KB Ok! 1474 queries used.
6 Correct 122 ms 588 KB Ok! 1563 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 596 KB Ok! 1583 queries used.
2 Correct 130 ms 640 KB Ok! 1597 queries used.