oj.uz

Submission #725076

# Submission time Handle Problem Language Result Execution time Memory
725076 2023-04-16T18:57:21 Z FatihSolak ICC (CEOI16_icc) C++17
100 / 100
 147 ms 736 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);
                }
            }
            solve(comps);
        }
    }

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 432 KB Ok! 94 queries used.
2 Correct 6 ms 468 KB Ok! 98 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 580 KB Ok! 554 queries used.
2 Correct 32 ms 584 KB Ok! 596 queries used.
3 Correct 46 ms 588 KB Ok! 595 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 568 KB Ok! 1397 queries used.
2 Correct 113 ms 636 KB Ok! 1472 queries used.
3 Correct 116 ms 640 KB Ok! 1545 queries used.
4 Correct 107 ms 736 KB Ok! 1488 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 640 KB Ok! 1399 queries used.
2 Correct 111 ms 624 KB Ok! 1501 queries used.
3 Correct 108 ms 640 KB Ok! 1520 queries used.
4 Correct 102 ms 576 KB Ok! 1483 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 568 KB Ok! 1494 queries used.
2 Correct 111 ms 632 KB Ok! 1475 queries used.
3 Correct 121 ms 568 KB Ok! 1528 queries used.
4 Correct 118 ms 608 KB Ok! 1536 queries used.
5 Correct 113 ms 572 KB Ok! 1489 queries used.
6 Correct 109 ms 576 KB Ok! 1550 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 636 KB Ok! 1523 queries used.
2 Correct 110 ms 636 KB Ok! 1472 queries used.