oj.uz

Submission #96068

# Submission time Handle Problem Language Result Execution time Memory
96068 2019-02-05T15:54:00 Z georgerapeanu ICC (CEOI16_icc) C++11
90 / 100
 284 ms 720 KB 
#include "icc.h"
 
#include <algorithm>
#include <ctime>
#include <cstdlib>
#include <vector>
#include <cstdio>
#include <iostream>
 
using namespace std;
 
const int NMAX = 1e2;

vector<vector<int>> components;
int label[NMAX + 5];
 
int a[NMAX + 5],len_a;
int b[NMAX + 5],len_b;
int lg2[NMAX + 5];


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);
}
 
void run(int n){
    lg2[0] = -1;
    for(int i = 1;i <= n;i++){
        lg2[i] = 1 + lg2[i >> 1];
        components.push_back({i});    
    } 
    for(int t = 1;t < n;t++){
        int last_comp_bit = lg2[(int)components.size() - 1];
        for(int x = 0;x < (int)components.size();x++){
            for(int i = 0;i < (int)components[x].size();i++){
                label[components[x][i]] = x;
            }
        }

        int m1 = 0;
        int m2 = 0;
        int xo = 0;

        for(int b = 0;b <= last_comp_bit;b++){
            vector<int> v1,v2;
            for(int i = 1;i <= n;i++){
                if((label[i] >> b) & 1){
                    v1.push_back(i);
                }
                else{
                    v2.push_back(i);
                }
            }
            
            xo |= my_query(v1,v2) << b;
        }

        int pos = 0;

        for(int b = 0;b <= last_comp_bit;b++){
            if((xo >> b) & 1){
                m1 = 1 << b;
                pos = b;
                break;
            }
        }

        for(int b = 0;b <= last_comp_bit;b++){
            if(b == pos){
                continue;
            }
            m2 |= ((((xo >> b) & 1)) << b);

            vector<int> v1,v2;

            for(int i = 1;i <= n;i++){
                if(((label[i] >> pos) & 1) == 1 && (((1 << (b + 1)) - 1) & label[i]) == (((1 << (b + 1)) - 1) & m1)){
                    v1.push_back(i);
                }
                else if(((label[i] >> pos) & 1) == 0 && (((1 << (b + 1)) - 1) & label[i]) == (((1 << (b + 1)) - 1) & m2)){
                    v2.push_back(i);
                }
            }

            if(my_query(v1,v2) == 0){
                m1 ^= (1 << b);
                m2 ^= (1 << b);
            }
        }
        
        int fst_comp = m1;
        int snd_comp = m2;
       
        int pref1 = -1,pref2 = -1;

        for(int b = 7;b >= 0;b--){
            if(pref1 + (1 << b) < (int)components[fst_comp].size()){
                vector<int> v;
                for(int i = 0;i <= pref1 + (1 << b);i++){
                    v.push_back(components[fst_comp][i]);
                }
                if(my_query(components[snd_comp],v) == 0){
                    pref1 += (1 << b);
                }
            }
        }
        
        for(int b = 7;b >= 0;b--){
            if(pref2 + (1 << b) < (int)components[snd_comp].size()){
                vector<int> v;
                for(int i = 0;i <= pref2 + (1 << b);i++){
                    v.push_back(components[snd_comp][i]);
                }
                if(my_query(components[fst_comp],v) == 0){
                    pref2 += (1 << b);
                }
            }
        }

        int u = components[fst_comp][pref1 + 1];
        int v = components[snd_comp][pref2 + 1];
        
        setRoad(u,v);
        
        for(auto it:components[fst_comp]){
            components[snd_comp].push_back(it);
        }
        swap(components[fst_comp],components.back());
        components.pop_back();
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 504 KB Ok! 135 queries used.
2 Correct 9 ms 504 KB Ok! 135 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 552 KB Ok! 709 queries used.
2 Correct 48 ms 504 KB Ok! 633 queries used.
3 Correct 49 ms 588 KB Ok! 694 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 560 KB Ok! 1712 queries used.
2 Correct 132 ms 504 KB Ok! 1482 queries used.
3 Correct 284 ms 720 KB Ok! 1719 queries used.
4 Correct 145 ms 604 KB Ok! 1688 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 504 KB Ok! 1710 queries used.
2 Correct 142 ms 568 KB Ok! 1711 queries used.
3 Correct 140 ms 568 KB Ok! 1699 queries used.
4 Correct 154 ms 632 KB Ok! 1718 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 504 KB Ok! 1670 queries used.
2 Correct 142 ms 504 KB Ok! 1694 queries used.
3 Correct 136 ms 660 KB Ok! 1646 queries used.
4 Correct 146 ms 504 KB Ok! 1715 queries used.
5 Correct 144 ms 632 KB Ok! 1708 queries used.
6 Correct 146 ms 564 KB Ok! 1715 queries used.

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 137 ms 688 KB Too many queries! 1692 out of 1625
2 Halted 0 ms 0 KB -