Submission #1154482

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154482		salmon	Toxic Gene (NOI23_toxic)	C++20	100 / 100	14 ms	328 KiB

toxic

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

char type[301];
vector<int> v;
vector<int> pro;
vector<int> trans;

vector<vector<int>> segregate(vector<int> v, int n, int l){
    vector<vector<int>> ans;

    int cont = 0;
    for(int i = 0; i < n ; i++){
        if(cont == v.size()) break;

        vector<int> temp;

        for(int j = 0; j < l; j++){
            if(cont == v.size()) break;
            temp.push_back(v[cont]);
            cont++;
        }

        ans.push_back(temp);
    }

    return ans;
}

int fquery(vector<int> v){
    for(int i = 0; i < v.size(); i++){
        v[i] = trans[v[i]];
    }
    return query_sample(v);
}

int squery(vector<int> v){
    vector<int> sas;
    vector<int> ind;
    int sise = v.size();
    int two = 1;
    while(!pro.empty() && v.size() + two <= 300){
        //printf("%d %d %d\n",pro.size(),fquery(v),v.size());
        if(type[pro.back()] != 0){
            pro.pop_back();
            continue;
        }
        sas.push_back(two);
        two *= 2;
        ind.push_back(pro.back());
        pro.pop_back();

        for(int i = 0; i < sas.back(); i++){
            v.push_back(ind.back());
        }
    }

    int num = fquery(v);

    if(num != v.size()){
        while(!ind.empty()){
            if(num >= sas.back()){
                num -= sas.back();
                type[ind.back()] = 'S';
            }
            else{
                type[ind.back()] = 'R';
            }
            sas.pop_back();
            ind.pop_back();
        }
    }
    else{
		for(int j : ind) pro.push_back(j);
        return sise;
    }

    return num;
}

int oquery(vector<int> v){
	vector<int> sas;
    vector<int> ind;
    int sise = v.size();
    while(!pro.empty() && v.size() + v.size() <= 300){
        //printf("%d %d %d\n",pro.size(),fquery(v),v.size());
        if(type[pro.back()] != 0){
            pro.pop_back();
            continue;
        }
        sas.push_back(v.size());
        ind.push_back(pro.back());
        pro.pop_back();

        for(int i = 0; i < sas.back(); i++){
            v.push_back(ind.back());
        }
    }

    int num = fquery(v);

    if(num != v.size()){
        while(!ind.empty()){
            if(num >= sas.back()){
                num -= sas.back();
                type[ind.back()] = 'S';
            }
            else{
                type[ind.back()] = 'R';
            }
            sas.pop_back();
            ind.pop_back();
        }
    }
    else{
		for(int j : ind) pro.push_back(j);
        return sise;
    }

    return num;
}


int iquery(vector<int> v){
    vector<int> ind;
    vector<int> sas;

    int num = 0;
    int N = v.size();
    int sise = N;
    for(int i = 1; i < N; i++){
        int cont = (N-i);
        for(int j = 0; j < i; j++){
            cont = cont * 2 + 1;
        }
        if( cont > 300){
            break;
        }
        num = i;
    }

    ind.push_back(v[0]);
    sas.push_back(1);

    for(int i = 0; i < num; i++){
        ind.push_back(v.back());
        v.pop_back();
    }

    for(int i = 1; i <= num; i++){
        sas.push_back(v.size() + 1);
        for(int j = 0; j < sas.back(); j++){
            v.push_back(ind[i]);
        }
    }

    num = oquery(v);

    if(num != v.size()){
        while(!ind.empty()){
            if(num >= sas.back()){
                num -= sas.back();
                type[ind.back()] = 'S';
            }
            else{
                type[ind.back()] = 'R';
            }
            sas.pop_back();
            ind.pop_back();
        }
        return 0;
    }
    else{
        return sise;
    }
}

void findtoxicsub(vector<int> ve, int t){
    /*if(squery(ve) == ve.size()){
        for(int i : ve){
            pro.push_back(i);
        }
        return;
    }*/
    if(ve.size() == 1){
		if(squery(ve) == 0) type[ve[0]] = 'T';
		return;
    }

    if(t > ve.size()){
        t = ve.size();
    }

    int past = ve.size();
    int num = (ve.size() + 1)/2 ;
    int two = 1;

    while(num >= t && num > 1){
        two = two * 2;
        past = num;
        num = (num + 1)/2;
    }

    vector<vector<int>> pros = segregate(ve,past,two);
    vector<vector<int>> next;
    vector<int> ukown;

    for(int i = 0; i < pros.size(); i++){
        if(squery(pros[i]) != pros[i].size()){
            next.push_back(pros[i]);
        }
        else{
            for(int j : pros[i]){
                pro.push_back(j);
            }
        }
    }

    while(next.size() != 0){
        swap(pros,next);
        next.clear();

        for(int i = 0; i < pros.size(); i++){
            vector<int> temp;

            for(int j: pros[i]){
                if(type[j] != 'S') temp.push_back(j);
			}
			pros[i] = temp;
			temp.clear();

            if(pros[i].size() == 0){
                t++;
                t--;
            }
            else if(pros[i].size() == 1){
                t--;
                type[pros[i][0]] = 'T';
            }
            else{
                for(int j = 0; j <  pros[i].size()/2 ; j++){
                    temp.push_back(pros[i][j]);
                }

                if(squery(temp) == temp.size()){
                    for(int i : temp){
                        pro.push_back(i);
                    }
                    temp.clear();
                    for(int j = pros[i].size()/2; j <  pros[i].size(); j++){
                        temp.push_back(pros[i][j]);
                    }
                    next.push_back(temp);
                }
                else{
                    next.push_back(temp);
                    for(int j = pros[i].size()/2; j <  pros[i].size(); j++){
                        ukown.push_back(pros[i][j]);
                    }
                }
            }
        }
    }

    if(!ukown.empty()) findtoxicsub(ukown,t);
}

void findtoxic(vector<int> ve, int t){
    int past = ve.size();
    int num = (ve.size() + 1)/2 ;
    int two = 1;

    while(num >= t && num > 1){
        two = two * 2;
        past = num;
        num = (num + 1)/2;
    }

    vector<vector<int>> pros = segregate(ve,past,two);
    vector<vector<int>> next;
    vector<int> ukown;

    for(int i = 0; i < pros.size(); i++){
        if(iquery(pros[i]) != pros[i].size()){
            next.push_back(pros[i]);
        }
        else{
            for(int j : pros[i]){
                pro.push_back(j);
            }
        }
    }

    while(next.size() != 0){
        swap(pros,next);
        next.clear();

        for(int i = 0; i < pros.size(); i++){
            vector<int> temp;

			for(int j: pros[i]){
                if(type[j] != 'S') temp.push_back(j);
			}
			pros[i] = temp;
			temp.clear();

            if(pros[i].size() == 0){
                t++;
                t--;
            }
            else if(pros[i].size() == 1){
                t--;
                type[pros[i][0]] = 'T';
            }
            else{
                for(int j = 0; j <  pros[i].size()/2 ; j++){
                    temp.push_back(pros[i][j]);
                }

                if(squery(temp) == temp.size()){
                    for(int i : temp){
                        pro.push_back(i);
                    }
                    temp.clear();
                    for(int j = pros[i].size()/2; j <  pros[i].size(); j++){
                        temp.push_back(pros[i][j]);
                    }
                    next.push_back(temp);
                }
                else{
                    next.push_back(temp);
                    for(int j = pros[i].size()/2; j <  pros[i].size(); j++){
                        ukown.push_back(pros[i][j]);
                    }
                }
            }
        }
    }

    if(!ukown.empty()) findtoxicsub(ukown,t);
}

void determine_type(int n){
    v.clear();
    trans.clear();

    trans.push_back(0);

    for(int i = 1; i <= n; i++){
        type[i] = 0;
        v.push_back(i);
        trans.push_back(i);
    }


    random_shuffle ( trans.begin() + 1, trans.end());
	random_shuffle ( trans.begin() + 1, trans.end());
	random_shuffle ( trans.begin() + 1, trans.end());

	pro.clear();

    findtoxic(v,30);
    int p;

    for(int i = 1; i <= n; i++){
        if(type[i] == 'T'){
            p = i;
        }
    }
    v.clear();
    while(!pro.empty()){
        if(type[pro.back()] != 0){
            pro.pop_back();
        }
        squery(vector<int>{p});
    }

	for(int i = 1; i <= n; i++){
		answer_type(trans[i], type[i]);
	}
}

• Subtask 1: 100 / 100