oj.uz

답안 #148274

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
148274 2019-08-31T19:35:58 Z 12tqian CEOI16_icc (CEOI16_icc) C++14
100 / 100
 151 ms 744 KB 
#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include "icc.h"

using namespace std;
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

const double PI = 4 * atan(1);

#define sz(x) (int)(x).size()
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair <int, int>
#define vi vector<int>
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define vpi vector<pair<int, int>>
#define vpd vector<pair<double, double>>
#define pd pair<double, double>

#define f0r(i,a) for(int i=0;i<a;i++)
#define f1r(i,a,b) for(int i=a;i<b;i++)
#define trav(a, x) for (auto& a : x)

template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {
  cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";
}

void fast_io(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
}
void io(string taskname){
    string fin = taskname + ".in";
    string fout = taskname + ".out";
    const char* FIN = fin.c_str();
    const char* FOUT = fout.c_str();
    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);
    fast_io();
}
template<int SZ> struct DSU{
    int par[SZ], sz[SZ];
    DSU(){
        for(int i = 0; i<SZ; i++){
            par[i] = i;
            sz[i] = 1;
        }
    }
    int get(int x){
        if(par[x] != x){
            par[x] = get(par[x]);
        }
        return par[x];
    }
    bool unite(int x, int y){
        x = get(x);
        y = get(y);
        if(x == y){
            return false;
        }
        if(sz[x] < sz[y]){
            swap(x, y);
        }
        sz[x] += sz[y];
        par[y] = x;
        return true;
    }
};
const int MAX = 1e2 + 5;
DSU<MAX> t;
int n;
vector<vi> groups;
///grader
/*
void setRoad(int i, int j){
    cout << "Set Road: " << i << " " << j << endl;
    return;
}
bool query(int sz_a, int sz_b, vi a, vi b){
    cout << a << " " << b << endl;
    int res;
    cin >> res;
    return res;
}*/
void answer(int i, int j){
    setRoad(i+1, j+1);
    t.unite(i, j);
}
int arr1[MAX], arr2[MAX];
bool ask(vi& a, vi& b){
    f0r(i, sz(a)) arr1[i] = a[i] + 1;
    f0r(i, sz(b)) arr2[i] = b[i] + 1;
    return query(sz(a), sz(b), arr1, arr2);
    /*vi v1;
    vi v2;
    for(int x: a) v1.eb(x+1);
    for(int x: b) v2.eb(x+1);
    return query(sz(a), sz(b), v1, v2);*/
}
pii connect(vi& a, vi& b){
    int lo = 0;
    int hi = sz(b) - 1;
    while(lo != hi){
        int mid = (lo + hi)/2;
        vi c;
        f1r(i,lo, mid+1) c.eb(b[i]);
        int val = ask(a, c);
        //cout << val << endl;
        if(val){
            hi = mid;
        }
        else{
            lo = mid+1;
        }
    }
  //  cout << "done" << endl;
    vi c;
    c.eb(b[lo]);
    lo = 0;
    hi = sz(a) - 1;
    while(lo != hi){
        int mid = (lo + hi)/2;
        vi d;
        f1r(i, lo, mid+1) d.eb(a[i]);
        int val = ask(d, c);
        //cout << val << endl;
        if(val){
            hi = mid;
        }
        else{
            lo = mid + 1;
        }
    }
    return mp(c[0], a[lo]);
}
vi convert(vi& a, vector<vi>& v){
    vi res;
    for(auto i: a){
        for(int j: v[i]) res.eb(j);
    }
    return res;
}
pii solve(vector<vi>& v){
    vector<vi> cur;
    vector<vi> nxt;
    vi tmp;
    f0r(i, sz(v)) tmp.eb(i);
    cur.eb(tmp);
    while(true){
        vi a;
        vi b;
        for(auto x: cur){
            f0r(i, sz(x)/2) a.eb(x[i]);
            f1r(i, sz(x)/2, sz(x)) b.eb(x[i]);
        }
        vi c = convert(a, v);
        vi d = convert(b, v);
        if(ask(c, d)){
            return connect(c, d);

        }
        else{
            nxt.clear();
            for(auto x: cur){
                vi tmp1;
                vi tmp2;
                if(sz(x)/2>1) f0r(i, sz(x)/2) tmp1.eb(x[i]);
                if(sz(x) -sz(x)/2  >1) f1r(i, sz(x)/2, sz(x)) tmp2.eb(x[i]);
                if(sz(tmp1)>0) nxt.eb(tmp1);
                if(sz(tmp2)>0) nxt.eb(tmp2);
            }
            cur.clear();
            for(auto x: nxt) cur.eb(x);
        }
    }
}
void run(int N){
    n = N;
    f0r(i, n){
        vi tmp;
        tmp.eb(i);
        groups.eb(tmp);
    }
    f0r(i, n-1){
        pii res = solve(groups);
        answer(res.f, res.s);
        set<int> vals;
        map<int, int> m;
        f0r(j, n){
            vals.insert(t.get(j));
        }
        int cnt = 0;
        for(auto x: vals){
            m[x] = cnt;
            cnt++;
        }
        groups.clear();
        f0r(j, sz(m)){
            vi tmp;
            groups.eb(tmp);
        }
        f0r(j, n){
            groups[m[t.get(j)]].eb(j);
        }
    }
}
/*
int main(){
    fast_io();
    int N;
    cin >> N;
    run(N);
    return 0;
}
*/

Compilation message

icc.cpp:1:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")
 
icc.cpp: In function 'void io(std::__cxx11::string)':
icc.cpp:53:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen(FIN, "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~
icc.cpp:54:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen(FOUT, "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 632 KB Ok! 105 queries used.
2 Correct 9 ms 636 KB Ok! 100 queries used.

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 504 KB Ok! 517 queries used.
2 Correct 46 ms 632 KB Ok! 577 queries used.
3 Correct 45 ms 632 KB Ok! 569 queries used.

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 142 ms 744 KB Ok! 1427 queries used.
2 Correct 147 ms 584 KB Ok! 1420 queries used.
3 Correct 151 ms 604 KB Ok! 1558 queries used.
4 Correct 142 ms 576 KB Ok! 1470 queries used.

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 144 ms 580 KB Ok! 1477 queries used.
2 Correct 143 ms 504 KB Ok! 1449 queries used.
3 Correct 146 ms 504 KB Ok! 1444 queries used.
4 Correct 143 ms 632 KB Ok! 1488 queries used.

Subtask #5
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 147 ms 632 KB Ok! 1433 queries used.
2 Correct 147 ms 580 KB Ok! 1425 queries used.
3 Correct 148 ms 580 KB Ok! 1461 queries used.
4 Correct 149 ms 592 KB Ok! 1529 queries used.
5 Correct 143 ms 588 KB Ok! 1485 queries used.
6 Correct 150 ms 588 KB Ok! 1544 queries used.

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 147 ms 576 KB Ok! 1449 queries used.
2 Correct 148 ms 580 KB Ok! 1420 queries used.