Submission #917765

#	Time	Username	Problem	Language	Result	Execution time	Memory
917765		JakobZorz	ICC (CEOI16_icc)	C++17	0 / 100	210 ms	888 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);
}
 
set<int>nodes[100];
//set<pair<int,int>>conns;
 
void run(int n){
    for(int i=0;i<n;i++){
        nodes[i].clear();
    }
    for(int _i=1;_i<n;_i++){
        int res1=-1,res2=-1;
        for(int i=0;i<n;i++){
            vector<int>nbs;
            for(int k=0;k<n;k++){
                if(k==i)
                    continue;
                
                if(nodes[i].count(k)==0)
                    nbs.push_back(k);
            }
            if(query({i},nbs)){
                if(res1==-1)
                    res1=i;
                else if(res2==-1)
                    res2=i;
                else
                    abort();
            }
        }
        
        nodes[res1].insert(res2);
        nodes[res2].insert(res1);
        set_road(res1,res2);
    }
    
    /*conns.clear();
    for(int _i=1;_i<n;_i++){
        pair<int,int>res;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(conns.count({i,j})==0&&query({i},{j})){
                    conns.insert({i,j});
                    res={i,j};
                    goto break2;
                }
            }
        }
        break2:
        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 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";
                exit(1);
            }
            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=15;
    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);
}
 
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<100;i++){
        srand(i);
        solve();
    }
    return 0;
}
#endif

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