Submission #212623

#	Time	Username	Problem	Language	Result	Execution time	Memory
212623		ereonzis	Chameleon's Love (JOI20_chameleon)	C++17	100 / 100	44 ms	436 KiB

chameleon

#include "chameleon.h"
#include <bits/stdc++.h>
using namespace std;


using LL = long long int;
using uLL = unsigned long long int;
using uint = unsigned int;
using ld = long double;

const int MAXN = 1007;

vector <int> group[MAXN];
vector <int> structure[4];
int ans[MAXN], beloved[MAXN], beloving[MAXN];
vector <vector <int> > indices = {{0, 1}, {0, 2}};
vector <int> not_present = {2, 1};


vector <int> sub_vector(int l, int r, vector <int> &w){
    if(l > r){
        vector <int> res;
        return res;
    }
    vector <int> res(r-l);
    for(int i = l; i < r; i++){
        res[i-l] = w[i];
    }
    return res;
}

int binarysearch(int l, int r, int id, int g){
    //cout << "G " << id << " " << g << " " << l << " " << r << '\n';
    while(l+1 < r){
        int mid = (l+r)>>1;
        //cout << l << " " << mid << " " << r << '\n';
        vector <int> temp = sub_vector(l+1, mid+1, structure[g]);
        temp.push_back(id);
        if(Query(temp) == int(temp.size())){
            l = mid;
        }
        else{
            r = mid;
        }
    }
    return r;
}

void update(int id){
    //cout << "ID " << id << '\n';
    bool czy = false;
    int licz = 0;
    for(int g = 0; g < 4; g++){
        vector <int> temp = structure[g];
        temp.push_back(id);
        if(licz == 3 || structure[g].empty() || Query(temp) == int(temp.size())){
            if(!czy){
                structure[g].push_back(id);
                //cout << "ADD " << g << " " << id << '\n';
                czy = true;
            }
        }
        else{
            int l = -1;
            int r = int(structure[g].size())-1;
            do{
                int x = binarysearch(l, r, id, g);
                group[structure[g][x]].push_back(id);
                group[id].push_back(structure[g][x]);
                //cout << "UP " << structure[g][x] << '\n';
                l = x;
                temp = sub_vector(l+1, r+1, structure[g]);
                temp.push_back(id);
                licz++;
                //cout << (licz < 3) << " " << (l < r) << '\n';
            }while(licz < 3 && l < r && Query(temp) < int(temp.size()));
        }
    }
    
}

void make_edge(int id){
    if(group[id].size() == 1){
        return;
    }
    /*cout << "GROUP " << id << '\n';
    for(auto x: group[id]){
        cout << x << " ";
    }
    cout << '\n';*/
    for(int i = 0; i < 2; i++){
        vector <int> temp = {id, group[id][indices[i][0]], group[id][indices[i][1]]};
        if(Query(temp) == 1){
            beloved[id] = group[id][not_present[i]];
            beloving[group[id][not_present[i]]] = id;
            return;
        }
    }
    beloved[id] = group[id][0];
    beloving[group[id][0]] = id;
    return;
}
void process_ans(int id){
    for(auto x: group[id]){
        if(x != beloved[id] && x != beloving[id]){
            ans[id] = x;
        }
    }
}


void Solve(int N){
    vector <int> tab(2*N);
    iota(tab.begin(), tab.end(), 1);
    srand(N);
    random_shuffle(tab.begin(), tab.end());
    for(auto x: tab){
        update(x);
    }
    for(int i = 1; i <= 2*N; i++){
        make_edge(i);
    }
    for(int i = 1; i <= 2*N; i++){
        process_ans(i);
    }
    /*for(int i = 1; i <= 2*N; i++){
        cout << ans[i] << '\n';
    }*/
    for(int i = 1; i <= 2*N; i++){
        if(i < ans[i]){
            Answer(i, ans[i]);
        }
    }
    
}

• Subtask 1: 4 / 4
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36