oj.uz

Submission #146401

# Submission time Handle Problem Language Result Execution time Memory
146401 2019-08-23T18:58:05 Z 12tqian Carnival (CEOI14_carnival) C++14
100 / 100
 29 ms 452 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>

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();
}
const int MAX = 155;
int res[MAX];

int par[MAX], sz[MAX];
void init(){
    for(int i = 0; i<MAX; 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){
   // cout << x << " united " << y << endl;
    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;
}

int ask(vi x){
    sort(all(x));
    cout << sz(x) << " ";
    for(int i: x) cout << i+1 << " ";
    cout << endl;
    int ret;
    cin >> ret;
    return ret;
}
vi comb(vi a, int b){
    vi ret;
    for(int x: a) ret.eb(x);
    ret.eb(b);
    return ret;
}
vi range(int l, int r){
    vi ret;
    f1r(i, l, r+1) ret.eb(i);
    return ret;
}
int val(int l, int r){
    set<int> s;
    f1r(i, l, r+1) s.insert(get(i));
    return sz(s);
}
void check(int x, int l, int r){
    if(ask(comb(range(l, r), x)) != val(l, r)){
        return;
    }
    int lo = l;
    int hi = r;
    while(abs(hi - lo)>1){
        int m = (lo + hi)/2;
        bool isTrue = (ask(comb(range(lo,m), x)) == val(lo, m));
        if(isTrue){
            hi = m;
        }
        else{
            lo = m+1;
        }
    }
    if(lo>hi) swap(lo, hi);
    if(ask(comb(range(lo, lo), x)) == 1){
        unite(lo, x);
    }
    else unite(hi, x);

}
void divide(int l, int r){
    if(l == r) return;
    if(r<l) return;
    if(r-l == 1){
        int res = ask(range(l, r));
        if(res == 2) return;
        else unite(l, r);
        return;
    }
    int m = (l + r)/2;
    divide(l, m);
    divide(m+1, r);
    f1r(i, l, m+1){
        check(i, m+1, r);
    }
}
unordered_map<int, int> um;
int main(){
    fast_io();
    int n;
    cin >> n;
    init();
    divide(0, n-1);
    set<int> s;
    vi ans;
    f0r(i, n){
        //cout << get(i) << " ";
        ans.eb(get(i));
        s.insert(get(i));
    }
    int cnt = 0;
    for(auto x: s){
        um[x] = cnt;
        cnt++;
    }
    cout << 0 << " ";
    for(int x: ans) cout << um[x]+1 << " ";
    cout << endl;
    return 0;
}

Compilation message

carnival.cpp:1:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")
 
carnival.cpp: In function 'void io(std::__cxx11::string)':
carnival.cpp:52: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);
     ~~~~~~~^~~~~~~~~~~~~~~~~
carnival.cpp:53: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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 376 KB Output is correct
2 Correct 16 ms 248 KB Output is correct
3 Correct 11 ms 424 KB Output is correct
4 Correct 6 ms 332 KB Output is correct
5 Correct 16 ms 332 KB Output is correct
6 Correct 27 ms 252 KB Output is correct
7 Correct 23 ms 248 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 248 KB Output is correct
2 Correct 13 ms 452 KB Output is correct
3 Correct 10 ms 248 KB Output is correct
4 Correct 11 ms 244 KB Output is correct
5 Correct 16 ms 332 KB Output is correct
6 Correct 27 ms 248 KB Output is correct
7 Correct 18 ms 376 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 248 KB Output is correct
2 Correct 26 ms 376 KB Output is correct
3 Correct 16 ms 336 KB Output is correct
4 Correct 10 ms 416 KB Output is correct
5 Correct 15 ms 332 KB Output is correct
6 Correct 28 ms 376 KB Output is correct
7 Correct 16 ms 248 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 376 KB Output is correct
2 Correct 29 ms 248 KB Output is correct
3 Correct 13 ms 248 KB Output is correct
4 Correct 11 ms 248 KB Output is correct
5 Correct 21 ms 248 KB Output is correct
6 Correct 12 ms 332 KB Output is correct
7 Correct 12 ms 332 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 376 KB Output is correct
2 Correct 27 ms 380 KB Output is correct
3 Correct 15 ms 328 KB Output is correct
4 Correct 15 ms 248 KB Output is correct
5 Correct 22 ms 332 KB Output is correct
6 Correct 17 ms 336 KB Output is correct
7 Correct 7 ms 336 KB Output is correct