oj.uz

Submission #46012

# Submission time Handle Problem Language Result Execution time Memory
46012 2018-04-17T01:16:57 Z sorry_Benq Carnival (CEOI14_carnival) C++17
100 / 100
 29 ms 588 KB 
#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;
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
template<typename T>
ostream& operator<< (ostream& out, const pair<T, T>& v) {
    out << "{" << v.first << ", " << v.second << "}";
    return out;
}

template<typename T>
ostream& operator<< (ostream& out, const vector<T>& v) {
    out << "[";
    size_t last = v.size() - 1;
    for(size_t i = 0; i < v.size(); ++i) {
        out << v[i];
        if (i != last) 
            out << ", ";
    }
    out << "]";
    return out;
}

template<typename T>
ostream& operator<< (ostream& out, const set<T>& v) {
    out << "[";
    auto pen = v.end();
    pen--;
    for (auto it = v.begin(); it != v.end(); it++){
		out << *it;
		if (it != pen){
			out << ", ";
		}
	}
	out << "]";
    return out;
}

template<typename T>
ostream& operator<< (ostream& out, const Tree<T>& v) {
    out << "[";
    auto pen = v.end();
    pen--;
    for (auto it = v.begin(); it != v.end(); it++){
		out << *it;
		if (it != pen){
			out << ", ";
		}
	}
	out << "]";
    return out;
}

map<int, set<int>> solve(vector<int> ppl){
	if (ppl.size() == 1){
		map<int, set<int>> m2;
		set<int> s; s.insert(ppl[0]);
		m2[1] = s;
		return m2;
	}
	vector<int> v1;
	vector<int> v2;
	for (int i = 0; i < ppl.size(); i++){
		if (i%2 == 0){
			v1.push_back(ppl[i]);
		}
		else{
			v2.push_back(ppl[i]);
		}
	}
	map<int, set<int>> m1 = solve(v1);
	map<int, set<int>> m2 = solve(v2);
	for (auto k: m2){
		int lo = 1;
		int hi = m1.size() + 1;
		while (lo != hi){
			int mid = (lo + hi)/2;
			vector<int> v;
			for (int i = 1; i <= mid; i++){
				for (int j: m1[i]) v.push_back(j);
			}
			for (int j: k.second){
				v.push_back(j);
			}
			cout << v.size() << ' ';
			for (int i: v){
				cout << i << ' ';
			}
			cout << endl;
			int res; cin >> res; 
			if (res == mid){
				hi = mid;
			}
			else{
				lo = mid + 1;
			}
		}
		for (auto u: k.second){
			m1[lo].insert(u);
		}
	}
	return m1;
}

int main(){
	int N; cin >> N;
	vector<int> v;
	for (int i = 1; i <= N; i++){
		v.push_back(i);
	}
	map<int, set<int>> m = solve(v);
	cout << 0;
	for (int i = 1; i <= N; i++){
		for (auto j: m){
			if (j.second.find(i) != j.second.end()){
				cout << ' ' << j.first; continue;
			}
		}
	}
	cout << endl;
}

Compilation message

carnival.cpp: In function 'std::map<int, std::set<int> > solve(std::vector<int>)':
carnival.cpp:89:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ppl.size(); i++){
                  ~~^~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 248 KB Output is correct
2 Correct 14 ms 440 KB Output is correct
3 Correct 14 ms 440 KB Output is correct
4 Correct 26 ms 440 KB Output is correct
5 Correct 5 ms 440 KB Output is correct
6 Correct 5 ms 444 KB Output is correct
7 Correct 11 ms 580 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 580 KB Output is correct
2 Correct 13 ms 580 KB Output is correct
3 Correct 15 ms 580 KB Output is correct
4 Correct 28 ms 580 KB Output is correct
5 Correct 9 ms 580 KB Output is correct
6 Correct 8 ms 580 KB Output is correct
7 Correct 9 ms 580 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 580 KB Output is correct
2 Correct 8 ms 580 KB Output is correct
3 Correct 18 ms 580 KB Output is correct
4 Correct 26 ms 580 KB Output is correct
5 Correct 8 ms 580 KB Output is correct
6 Correct 8 ms 580 KB Output is correct
7 Correct 16 ms 580 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 580 KB Output is correct
2 Correct 10 ms 580 KB Output is correct
3 Correct 25 ms 580 KB Output is correct
4 Correct 29 ms 580 KB Output is correct
5 Correct 11 ms 580 KB Output is correct
6 Correct 14 ms 580 KB Output is correct
7 Correct 15 ms 580 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 580 KB Output is correct
2 Correct 18 ms 584 KB Output is correct
3 Correct 15 ms 584 KB Output is correct
4 Correct 24 ms 588 KB Output is correct
5 Correct 16 ms 588 KB Output is correct
6 Correct 21 ms 588 KB Output is correct
7 Correct 26 ms 588 KB Output is correct