Submission #1244564

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244564		m5588ohammed	ICC (CEOI16_icc)	C++20	0 / 100	5 ms	584 KiB

icc

#include "icc.h"
#include<bits/stdc++.h>
using namespace std;
vector <int> gr[1001];
int Query(vector <int> a,vector<int> b){
    const int sizA=a.size(),sizB=b.size();
    int A[sizA], B[sizB];
    for(int i=0;i<sizA;i++) A[i]=a[i];
    for(int i=0;i<sizB;i++) B[i]=b[i];
    int num=query(sizA,sizB,A,B);
    return num;
}
int Query2(vector <int> A,vector<int> B){
    vector <int> a,b;
    for(int i:A){
        for(int j:gr[i]) a.push_back(j);
    }
    for(int i:B){
        for(int j:gr[i]) b.push_back(j);
    }
    return Query(a,b);
}
pair<vector <int>,vector <int>> Svec(vector <int> a){
    vector <int> A1,A2;
    for(int i=0;i<(int)a.size()/2;i++) A1.push_back(a[i]);
    for(int i=(int)a.size()/2;i<a.size();i++) A2.push_back(a[i]);
    return {A1,A2};
}

array<int,2> Solve_Case1_2(vector <vector<int>> grA,vector <vector<int>> grB);
array<int,2> Solve_Case2(vector <int> grA,vector <int> grB);
array<int,2> Solve_Case3(int A,int B);

array<int,2> Solve_Case1(vector <vector<int>> grA,vector <vector<int>> grB){
    vector <int> allA,allB;
    // cout<<"grA "; 
    for(vector <int> v:grA){
        for(int i:v) {
            allA.push_back(i);
            // cout<<i<<" ";
        }
    }
    // cout<<endl;
    // cout<<"grB "; 
    for(vector <int> v:grB){
        for(int i:v){
            allB.push_back(i);
            // cout<<i<<" ";
        }
    }
    // cout<<endl;
    if(Query2(allA,allB)==0){
        vector <vector<int>> nwA,nwB;
        for(vector <int> v:grA){
            auto [cA,cB]=Svec(v);
            nwA.push_back(cA);
            nwB.push_back(cB);
        } 
        for(vector <int> v:grB){
            auto [cA,cB]=Svec(v);
            nwA.push_back(cA);
            nwB.push_back(cB);
        } 
        return Solve_Case1(nwA,nwB);
    }
    else{
        //cout<<"YES"<<endl;
        return Solve_Case1_2(grA,grB);
    }
}
array<int,2> Solve_Case1_2(vector <vector<int>> grA,vector <vector<int>> grB){
    int l=0,r=grA.size()-1;
    while(l<r){
        int mid=(l+r)/2;
        vector <int> allA,allB;
        for(int j=l;j<=r;j++){
            for(int i:grA[j]) allA.push_back(i);
        }
        for(int j=l;j<=r;j++){
            for(int i:grB[j]) allB.push_back(i);
        }
        if(Query2(allA,allB)==1) r=mid;
        else l=mid+1;
    }
    return Solve_Case2(grA[r],grB[r]);
}
array<int,2> Solve_Case2(vector <int> grA,vector <int> grB){
    if(grA.size()==1&&grB.size()==1) return Solve_Case3(grA[0],grB[0]);
    if(grA.size()==1) swap(grA,grB);
    
    auto [grA1,grA2]=Svec(grA);
    auto [grB1,grB2]=Svec(grB);

    if(Query2(grA1,grB)==1){
        if(grB.size()==1) return Solve_Case2(grA1,grB);
        if(Query2(grA1,grB1)==1) return Solve_Case2(grA1,grB1);
        else return Solve_Case2(grA1,grB2);
    }
    else{
        if(grB.size()==1) return Solve_Case2(grA2,grB);
        if(Query2(grA2,grB1)==1) return Solve_Case2(grA2,grB1);
        else return Solve_Case2(grA2,grB2);   
    }

}
array<int,2> Solve_Case3(int A,int B){
    //cout<<A<<" "<<B<<endl;
    int l=0,r=gr[A].size()-1,posA=-1,posB=-1;    
    while(l<r){
        int mid=(l+r)/2;
        vector <int> qu;
        for(int i=l;i<=mid;i++) qu.push_back(gr[A][i]);
        if(Query(qu,gr[B])==1) r=mid;
        else l=mid+1;
    }
    posA=gr[A][r];
    l=0,r=gr[B].size()-1;
    while(l<r){
        int mid=(l+r)/2;
        vector <int> qu;
        for(int i=l;i<=mid;i++) qu.push_back(gr[B][i]);
        if(Query(qu,gr[A])==1){
            posB=mid;
            r=mid;
        }
        else l=mid+1;
    }
    posB=gr[B][r];
    return {posA,posB};
}
set <int> leaders;
int parent[1001];
int find(int i){
    if(parent[i]==i) return i;
    return parent[i]=find(parent[i]);
}
void merge(int a,int b){
    a=find(a),b=find(b);
    leaders.erase(b);
    while(gr[b].size()!=0){
        gr[a].push_back(gr[b].back());
        gr[b].pop_back();
    }
    parent[b]=a;
    return;
}
void run(int n){
    //cout<<"YES"<<endl;
    for(int i=1;i<=n;i++){
        leaders.insert(i);
        parent[i]=i;
        gr[i].push_back(i);
    }
    int k=n-1;
    while(k--){
        vector <int> v;
        for(int i:leaders) v.push_back(i);
        vector <vector<int>> a,b;
        a.push_back(Svec(v).first); 
        b.push_back(Svec(v).second); 

        auto [s,e]=Solve_Case1(a,b);
        // cout<<s<<" "<<e<<endl;
        merge(s,e);
        setRoad(s,e);
    }
    //g++ -std=c++17 grader.cpp solve.cpp -o exe && ./exe
    return;
}

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