oj.uz

Submission #94947

# Submission time Handle Problem Language Result Execution time Memory
94947 2019-01-25T12:03:05 Z georgerapeanu ICC (CEOI16_icc) C++11
18 / 100
 239 ms 632 KB 
#include "icc.h"

#include <algorithm>
#include <ctime>
#include <cstdlib>
#include <vector>
#include <cstdio>

using namespace std;

vector<vector<int>> components;

int a[200],len_a;
int b[200],len_b;
int c[200],len_c;
int d[200],len_d;

const int LIM = 2;

int my_query(vector<int> &c1,vector<int> &c2){
    
    len_a = 0;
    for(auto it:c1){
        a[len_a++] = it;
    }

    len_b = 0;
    for(auto it:c2){
        b[len_b++] = it;
    }

    if(len_a == 0 || len_b == 0){
        return 0;
    }

    return query(len_a,len_b,a,b);
}

int my_query(vector< vector<int> > &c1,vector< vector<int> > &c2){
    len_a = 0;
    for(auto it:c1){
        for(auto it2:it){
            a[len_a++] = it2;
        }
    }
    
    len_b = 0;
    for(auto it:c2){
        for(auto it2:it){
            b[len_b++] = it2;
        }
    }

    if(len_a == 0 || len_b == 0){
        return 0;
    }

    return query(len_a,len_b,a,b);
}

void run(int n){
    srand(time(NULL));
    for(int i = 1;i <= n;i++){
        components.push_back({i});    
    } 
    
    for(int t = 1;t < n;t++){
        random_shuffle(components.begin(),components.end());
        vector<vector<int>> c1,c2;
        for(int i = 0;i < (int)components.size() / 2;i++){
            c1.push_back(components[i]);
        }
        for(int i = (int)components.size() / 2;i < (int)components.size();i++){
            c2.push_back(components[i]);
        }

        while(c1.size() + c2.size() > LIM){

            while(my_query(c1,c2) == 0){
                random_shuffle(c1.begin(),c1.end());
                random_shuffle(c2.begin(),c2.end());
    
                vector<vector<int>> nc1,nc2;
            
                for(int i = 0;i < (int)c1.size() / 2;i++){
                    nc1.push_back(c1[i]);
                }

                for(int i = (int)c1.size() / 2;i < (int)c1.size();i++){
                    nc2.push_back(c1[i]);
                }

                for(int i = 0;i < (int)c2.size() / 2;i++){
                    nc1.push_back(c2[i]);
                }

                for(int i = (int)c2.size() / 2;i < (int)c2.size();i++){
                    nc2.push_back(c2[i]);
                }

                swap(c1,nc1);
                swap(c2,nc2);
            }

            vector<vector<int>> nc1,nc2,nc3,nc4;
            
            for(int i = 0;i < (int)c1.size() / 2;i++){
                nc1.push_back(c1[i]);
            }

            for(int i = (int)c1.size() / 2;i < (int)c1.size();i++){
                nc2.push_back(c1[i]);
            }

            for(int i = 0;i < (int)c2.size() / 2;i++){
                nc3.push_back(c2[i]);
            }

            for(int i = (int)c2.size() / 2;i < (int)c2.size();i++){
                nc4.push_back(c2[i]);
            }
        
            if(my_query(nc1,nc3)){
                swap(c1,nc1);
                swap(c2,nc3);
            }
            else if(my_query(nc1,nc4)){
                swap(c1,nc1);
                swap(c2,nc4);
            }
            else if(my_query(nc2,nc3)){
                swap(c1,nc2);
                swap(c2,nc3);
            }
            else{
                swap(c1,nc2);
                swap(c2,nc4);
            }
        }
        
        vector<int> fst_comp = c1[0];
        vector<int> snd_comp = c2[0];

        for(auto &it:components){
            if(it == snd_comp){
                swap(it,components.back());
            }
        }

        components.pop_back();

        for(auto &it:components){
            if(it == fst_comp){
                for(auto it2:snd_comp){
                    it.push_back(it2);
                }
            }
        }

        while((int)fst_comp.size() + (int)snd_comp.size() > LIM){
            vector<int> nc1,nc2,nc3,nc4;

            for(int i = 0;i < (int)fst_comp.size() / 2;i++){
                nc1.push_back(fst_comp[i]);
            }

            for(int i = (int)fst_comp.size() / 2;i < (int)fst_comp.size();i++){
                nc2.push_back(fst_comp[i]);
            }
            
            for(int i = 0;i < (int)snd_comp.size() / 2;i++){
                nc3.push_back(snd_comp[i]);
            }

            for(int i = (int)snd_comp.size() / 2;i < (int)snd_comp.size();i++){
                nc4.push_back(snd_comp[i]);
            }

            if(my_query(nc1,nc3)){
                swap(fst_comp,nc1);
                swap(snd_comp,nc3);
            }
            else if(my_query(nc1,nc4)){
                swap(fst_comp,nc1);
                swap(snd_comp,nc4);
            }
            else if(my_query(nc2,nc3)){
                swap(fst_comp,nc2);
                swap(snd_comp,nc3);
            }
            else{
                swap(fst_comp,nc2);
                swap(snd_comp,nc4);
            }
        }
        setRoad(fst_comp[0],snd_comp[0]);
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 504 KB Ok! 154 queries used.
2 Correct 10 ms 504 KB Ok! 156 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 564 KB Ok! 918 queries used.
2 Correct 71 ms 504 KB Ok! 1043 queries used.
3 Correct 70 ms 504 KB Ok! 1050 queries used.

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 203 ms 580 KB Too many queries! 2423 out of 2250
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 223 ms 632 KB Too many queries! 2501 out of 2000
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 239 ms 632 KB Too many queries! 2567 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 237 ms 632 KB Too many queries! 2548 out of 1625
2 Halted 0 ms 0 KB -