oj.uz

답안 #605039

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
605039 2022-07-25T12:28:43 Z Theo830 CEOI16_icc (CEOI16_icc) C++17
100 / 100
 198 ms 1076 KB 
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ll,ii>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///CEOI 2016 day 1
#include "icc.h"
/*
int query(int size_a, int size_b, int a[], int b[]){
    cout<<size_a<<" : ";
    f(i,0,size_a){
        cout<<a[i]<<" ";
    }
    cout<<"\n";
    cout<<size_b<<" : ";
    f(i,0,size_b){
        cout<<b[i]<<" ";
    }
    cout<<"\n";
    ll v;
    cin>>v;
    return v;
}
*/
ll par[1005];
ll find_par(ll a){
    if(par[a] == a){
        return a;
    }
    return par[a] = find_par(par[a]);
}
void enose(ll a,ll b){
    a = find_par(a);
    b = find_par(b);
    par[a] = b;
}
void run(int N){
    ll n = N;
    f(i,0,n+5){
        par[i] = i;
    }
    while(1){
        ll a = -1,b = -1;
        set<ll>com;
        vll exo[n+5];
        vll arr;
        f(i,1,n+1){
            exo[find_par(i)].pb(i);
            com.insert(find_par(i));
        }
        for(auto x:com){
            arr.pb(x);
        }
        vll AA,BB;
        set<ll>lathos[n+5];
        while(1){
            vll A[2];
            f(i,0,arr.size()){
                A[i % 2].pb(arr[i]);
            }
            arr = A[0];
            for(auto x:A[1]){
                arr.pb(x);
            }
            vll nA,nB;
            for(auto x:A[0]){
                for(auto y:exo[x]){
                    nA.pb(y);
                }
            }
            for(auto x:A[1]){
                for(auto y:exo[x]){
                    nB.pb(y);
                }
            }
            ll sa = nA.size();
            ll sb = nB.size();
            ll aa[sa],bb[sb];
            f(i,0,sa){
                aa[i] = nA[i];
            }
            f(i,0,sb){
                bb[i] = nB[i];
            }
            if(query(sa,sb,aa,bb) == 1){
                AA = nA;
                BB = nB;
                break;
            }
            else{
                for(auto x:A[0]){
                    for(auto y:A[1]){
                        lathos[x].insert(y);
                        lathos[y].insert(x);
                    }
                }
            }
        }
        ll l = 0,r = AA.size() - 1;
        ll pos = r + 1;
        while(l <= r){
            ll mid = (l+r)/2;
            ll sa = AA.size();
            ll sb = BB.size();
            ll aa[mid+1],bb[sb];
            f(i,0,mid+1){
                aa[i] = AA[i];
            }
            f(i,0,sb){
                bb[i] = BB[i];
            }
            if(query(mid+1,sb,aa,bb) == 1){
                r = mid - 1;
                pos = min(pos,mid);
            }
            else{
                l = mid + 1;
            }
        }
        a = AA[pos];
        vll C;
        for(auto x:BB){
            if(!lathos[a].count(x)){
                C.pb(x);
            }
        }
        BB = C;
        l = 0,r = BB.size() - 2;
        pos = r + 1;
        while(l <= r){
            ll mid = (l+r)/2;
            ll sa = AA.size();
            ll sb = BB.size();
            ll aa[sa],bb[mid+1];
            f(i,0,sa){
                aa[i] = AA[i];
            }
            f(i,0,mid+1){
                bb[i] = BB[i];
            }
            if(query(sa,mid+1,aa,bb) == 1){
                r = mid - 1;
                pos = min(pos,mid);
            }
            else{
                l = mid + 1;
            }
        }
        b = BB[pos];
        setRoad(a,b);
        enose(a,b);
    }
}
/*
int main(){
    run(4);
}
*/

Compilation message

icc.cpp: In function 'void run(int)':
icc.cpp:8:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define f(i,a,b) for(ll i = a;i < b;i++)
......
   76 |             f(i,0,arr.size()){
      |               ~~~~~~~~~~~~~~     
icc.cpp:76:13: note: in expansion of macro 'f'
   76 |             f(i,0,arr.size()){
      |             ^
icc.cpp:121:16: warning: unused variable 'sa' [-Wunused-variable]
  121 |             ll sa = AA.size();
      |                ^~
icc.cpp:151:16: warning: unused variable 'sb' [-Wunused-variable]
  151 |             ll sb = BB.size();
      |                ^~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 468 KB Ok! 100 queries used.
2 Correct 6 ms 468 KB Ok! 102 queries used.

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 468 KB Ok! 534 queries used.
2 Correct 39 ms 596 KB Ok! 645 queries used.
3 Correct 38 ms 604 KB Ok! 640 queries used.

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 140 ms 936 KB Ok! 1369 queries used.
2 Correct 198 ms 980 KB Ok! 1581 queries used.
3 Correct 160 ms 1076 KB Ok! 1540 queries used.
4 Correct 153 ms 948 KB Ok! 1434 queries used.

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 151 ms 960 KB Ok! 1409 queries used.
2 Correct 152 ms 952 KB Ok! 1404 queries used.
3 Correct 180 ms 960 KB Ok! 1564 queries used.
4 Correct 146 ms 852 KB Ok! 1423 queries used.

Subtask #5
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 175 ms 956 KB Ok! 1550 queries used.
2 Correct 185 ms 852 KB Ok! 1548 queries used.
3 Correct 171 ms 960 KB Ok! 1546 queries used.
4 Correct 166 ms 960 KB Ok! 1501 queries used.
5 Correct 165 ms 1068 KB Ok! 1400 queries used.
6 Correct 151 ms 960 KB Ok! 1434 queries used.

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 173 ms 852 KB Ok! 1542 queries used.
2 Correct 182 ms 960 KB Ok! 1605 queries used.