oj.uz

Submission #605670

# Submission time Handle Problem Language Result Execution time Memory
605670 2022-07-25T21:35:31 Z 2fat2code ICC (CEOI16_icc) C++17
0 / 100
 2 ms 468 KB 
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;

const int nmax = 105;

int par[nmax];
vector<int>componente[nmax];

void run(int n){
    for(int i=1;i<=n;i++){
        componente[i].push_back(i);
        par[i] = i;
    }
    int nrcomponente = n;
    vector<int>cautambinar_A, cautambinar_B;
    for(int i=1;i<n;i++){
        int bit = 0, xr = 0;
        while((1<<bit) <= nrcomponente){
            int a_sz = 0; vector<int>a;
            int b_sz = 0; vector<int>b;
            for(int j=1;j<=nrcomponente;j++){
                if(j & (1 << bit)){
                    a_sz += componente[j].size();
                    for(auto it : componente[j]) a.push_back(it);
                }
                else{
                    b_sz += componente[j].size();
                    for(auto it : componente[j]) b.push_back(it);
                }
            }
            if(query(a_sz, b_sz, a.data(), b.data()) == 1){
                xr += (1 << bit);
                cautambinar_A.clear();
                cautambinar_B.clear();
                for(int j=1;j<=nrcomponente;j++){
                    if(j & (1 << bit)){
                        for(auto it : componente[j]){
                            cautambinar_A.push_back(it);
                        }
                    }
                    else {
                        for(auto it : componente[j]){
                            cautambinar_B.push_back(j);
                        }
                    }
                }
            }
            ++bit;
        }
        int l = 0, r = cautambinar_A.size() - 1, ok = 0;
        vector<int>tz;
        while(l <= r){
            int mid = l + (r - l) / 2;
            tz.clear();
            for(int j=0;j<=mid;j++) tz.push_back(cautambinar_A[j]);
            if(query(tz.size(), cautambinar_B.size(), tz.data(), cautambinar_B.data())){
                ok = mid;
                r = mid - 1;
            }
            else{
                l = mid + 1;
            }
        }
        ok = cautambinar_A[ok];
        xr ^= par[ok];
        int ok2 = 0;
        l = 0, r = componente[xr].size() - 1;
        while(l <= r){
            int mid = l + (r - l) / 2;
            tz.clear();
            for(int j=0;j<=mid;j++){
                tz.push_back(componente[xr][j]);
            }
            if(query(1, tz.size(), &ok, tz.data()) == 1){
                ok2 = mid;
                l = mid + 1;
            }
            else{
                r = mid - 1;
            }
        }
        ok2 = cautambinar_B[ok2];
        int lmao = max(par[ok], par[ok2]);
        int slavic = min(par[ok], par[ok2]);
        for(int i=1;i<=n;i++){
            if(par[i] == lmao) par[i] = slavic;
            else if(par[i] > lmao){
                par[i]--;
            }
        }
        for(int j=1;j<=nrcomponente;j++) componente[j].clear();
        for(int j=1;j<=n;j++) componente[par[j]].push_back(j);
        setRoad(ok, ok2);
        nrcomponente--;
    }
}

Compilation message

icc.cpp: In function 'void run(int)':
icc.cpp:43:34: warning: unused variable 'it' [-Wunused-variable]
   43 |                         for(auto it : componente[j]){
      |                                  ^~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 468 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 468 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 468 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 468 KB Wrong road!
2 Halted 0 ms 0 KB -