제출 #367256

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
367256		mihai145	ICC (CEOI16_icc)	C++14	100 / 100	155 ms	700 KiB

icc

//
// Created by mihai145 on 16.02.2021.
//

#include <vector>
#include <cmath>
#include "icc.h"

using namespace std;

const int NMAX = 100;
int comp[NMAX + 2];

void run(int N) {
    for(int i = 1; i <= N; i++) {
        comp[i] = i - 1;
    }

    for(int c = N; c > 1; c--) {
        int log = log2(c);

        vector<int> A, B;

        for(int bit = 0; bit <= log; bit++) {
            vector<int> a, b;
            for(int i = 1; i <= N; i++) {
                if (comp[i] & (1 << bit))
                    a.push_back(i);
                else
                    b.push_back(i);
            }

            int q = query((int)a.size(), (int)b.size(), a.data(), b.data());
            if(q) {
                A = a;
                B = b;
                break;
            }
        }

        for(int step = 1; step <= 2; step++) {
            while((int)A.size() > 1) {
                vector<int> A1, A2;
                for(int i = 0; i < (int)A.size(); i++) {
                    if(i % 2 == 0) {
                        A1.push_back(A[i]);
                    } else {
                        A2.push_back(A[i]);
                    }
                }

                int q = query((int)A1.size(), (int)B.size(), A1.data(), B.data());

                if(q) {
                    A = A1;
                } else {
                    A = A2;
                }
            }

            swap(A, B);
        }

        setRoad(A[0], B[0]);

        int cA = comp[A[0]], cB = comp[B[0]];

        for(int i = 1; i <= N; i++)
            if(comp[i] == cA) {
                comp[i] = cB;
            }
        
        for(int i = 1; i <= N; i++)
            if(comp[i] == c - 1) {
                comp[i] = cA;
            }
    }
}

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 10 / 10