제출 #917773

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
917773		JakobZorz	ICC (CEOI16_icc)	C++17	100 / 100	102 ms	1108 KiB

icc

#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<limits.h>
#include<math.h>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<iomanip>
#include<cstring>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;
 
#ifndef JAKOB
#include"icc.h"
#else
int query(int size_a, int size_b, int a[], int b[]);
void setRoad(int a, int b);
#endif
 
bool query(vector<int>a,vector<int>b){
    if(a.empty()||b.empty())
        return false;
    for(int&i:a)
        i++;
    for(int&i:b)
        i++;
    return query((int)a.size(),(int)b.size(),&a[0],&b[0])==1;
}
 
void set_road(int a,int b){
    setRoad(a+1,b+1);
}
 
pair<int,int>get3(vector<int>s1,vector<int>s2){
    if(s1.size()==1)
        swap(s1,s2);
    if(s1.size()==1)
        return{s1[0],s2[0]};
    
    int ss=(int)s1.size();
    vector<int>a,b;
    for(int i=0;i<ss/2;i++)
        a.push_back(s1[i]);
    for(int i=ss/2;i<ss;i++)
        b.push_back(s1[i]);
    if(query(a,s2))
        return get3(a,s2);
    else
        return get3(b,s2);
}
 
pair<int,int>get1(vector<vector<vector<int>>>s){
    while(true){
        vector<vector<vector<int>>>s2;
        for(auto&i:s){
            if(i.size()==1)
                continue;
            int sz=(int)i.size();
            s2.emplace_back();
            for(int j=0;j<sz/2;j++)
                s2.back().push_back(i[j]);
            s2.emplace_back();
            for(int j=sz/2;j<sz;j++)
                s2.back().push_back(i[j]);
        }
        vector<int>a1,a2;
        for(int i=0;i<(int)s2.size();i++){
            for(auto&i1:s2[i]){
                for(int i2:i1){
                    if(i%2)
                        a2.push_back(i2);
                    else
                        a1.push_back(i2);
                }
            }
        }
        if(query(a1,a2)){
            return get3(a1,a2);
        }
        
        s=s2;
    }
}
 
void run(int n){
    vector<vector<int>>components;
    for(int i=0;i<n;i++)
        components.push_back({i});
    
    for(int _i=1;_i<n;_i++){
        auto res=get1({components});
        vector<int>nc;
        for(int i=0;i<(int)components.size();i++){
            bool has=false;
            for(int j:components[i]){
                if(j==res.first)
                    has=true;
            }
            if(has){
                for(int j:components[i])
                    nc.push_back(j);
                components.erase(components.begin()+i);
                break;
            }
        }
        for(int i=0;i<(int)components.size();i++){
            bool has=false;
            for(int j:components[i]){
                if(j==res.second)
                    has=true;
            }
            if(has){
                for(int j:components[i])
                    nc.push_back(j);
                components.erase(components.begin()+i);
                break;
            }
        }
        components.push_back(nc);
        set_road(res.first,res.second);
    }
}
 
#ifdef JAKOB
 
vector<pair<int,int>>gsteps;
set<pair<int,int>>gconns;
int gcstep;
int gqueries;
int gerr;
int gmqc;
 
int query(int size_a, int size_b, int a[], int b[]){
    sort(a,a+size_a);
    sort(b,b+size_b);
    {
        int i=0,j=0;
        while(i<size_a&&j<size_b){
            if(a[i]==b[j]){
                cout<<"NOT DISJOINT\n";
                abort();
            }
            if(a[i]<b[j])
                i++;
            else
                j++;
        }
    }
    
    gqueries++;
    
    for(int i=0;i<size_a;i++)
        for(int j=0;j<size_b;j++)
            if(gconns.count({a[i],b[j]})==1||gconns.count({b[j],a[i]})==1)
                return 1;
    
    return 0;
}
 
void gprocess_step(){
    gcstep++;
    gconns.insert(gsteps[gcstep]);
}
 
void setRoad(int a, int b){
    if(a<b)
        swap(a,b);
    if(a!=gsteps[gcstep].first||b!=gsteps[gcstep].second){
        cout<<"ERROR got "<<a<<" "<<b<<", expected "<<gsteps[gcstep].first<<" "<<gsteps[gcstep].second<<"\n";
        gerr++;
    }else
        cout<<"OK "<<a<<" "<<b<<"\n";
    gprocess_step();
}
 
void solve(){
    gconns.clear();
    gsteps.clear();
    gcstep=-1;
    gqueries=0;
    gerr=0;
    int n=100;
    vector<int>perm(n);
    for(int i=0;i<n;i++)
        perm[i]=i;
    for(int i=0;i<n;i++)
        swap(perm[i],perm[rand()%n]);
    for(int i=1;i<n;i++)
        gsteps.push_back({i,rand()%i});
    
    
    for(auto&i:gsteps){
        i.first=perm[i.first];
        i.second=perm[i.second];
        if(i.first<i.second)
            swap(i.first,i.second);
        i.first++;
        i.second++;
    }
    for(int i=0;i<n-1;i++)
        swap(gsteps[i],gsteps[rand()%(n-1)]);
    
    gprocess_step();
    run(n);
    cout<<"query count: "<<gqueries<<"\n";
    cout<<"error count: "<<gerr<<"\n";
    if(gerr)
        exit(0);
    gmqc=max(gmqc,gqueries);
}
 
int main(){
    ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
    //freopen("input.in","r",stdin);freopen("output.out","w",stdout);
    //int t=1;//cin>>t;
    //while(t--)solve();
    
    
    for(int i=0;i<50;i++){
        srand(i);
        solve();
    }
    cout<<"max queries: "<<gmqc<<"\n";
    return 0;
}
#endif

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