oj.uz

답안 #917769

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
917769 2024-01-28T18:12:35 Z JakobZorz CEOI16_icc (CEOI16_icc) C++17
7 / 100
 208 ms 608 KB 
#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();
    query({1},{0});
    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
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 604 KB Ok! 1016 queries used.
2 Correct 34 ms 604 KB Ok! 1012 queries used.

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 183 ms 604 KB Number of queries more than 5000 out of 2500
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 208 ms 604 KB Number of queries more than 4500 out of 2250
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 208 ms 608 KB Number of queries more than 4000 out of 2000
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 164 ms 608 KB Number of queries more than 3550 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 157 ms 604 KB Number of queries more than 3250 out of 1625
2 Halted 0 ms 0 KB -