oj.uz

Submission #1071979

# Submission time Handle Problem Language Result Execution time Memory
1071979 2024-08-23T12:57:09 Z pan Mechanical Doll (IOI18_doll) C++17
100 / 100
 114 ms 19196 KB 
#include <bits/stdc++.h>
//#include "bits_stdc++.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define input2(x, y) scanf("%lld%lld", &x, &y);
#define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
#define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define all(x) x.begin(), x.end()
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define FOR(i, x, n) for (ll i =x; i<=n; ++i) 
#define RFOR(i, x, n) for (ll i =x; i>=n; --i) 
using namespace std;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
//#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<pi, ll> pii;
typedef pair<pi, pi> piii;

vector<ll> a;
unordered_map<ll, vector<ll> > pos;
vector<int>  X, C, Y;
ll cnt = -1, fir = -1;

bool compare(pii a, pii b) {return a.s < b.s; }

void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y);


vector<pii> dfs(ll layer, ll tot)
{
	vector<pii> ret;
	ll now = ++cnt;
	if (layer==1)
	{
		ret.pb(mp(mp(now, 0), 2));
		if (tot==1) {X[now] = -fir-1; return ret;}
		ret.pb(mp(mp(now, 1), 1));
		return ret;
	}
	Y[now] = -cnt-2;
	vector<pii> ri = dfs(layer-1, tot);
	vector<pii> le;
	if (tot - (1LL << (layer-1)) > 0){ X[now] = -cnt-2; le = dfs(layer-1,tot - (1LL << (layer-1)));}
	else {X[now] = -fir-1;}
	for (ll i=0; i<le.size(); ++i) le[i].s = le[i].s*2 - 1;
	for (ll i=0; i<ri.size(); ++i) ri[i].s = ri[i].s*2;
	ret.resize(le.size() + ri.size());
	merge(all(le), all(ri), ret.begin());
	return ret;

}

void create_circuit(int M, std::vector<int> A)
{
	ll n = A.size();
	C.resize(M+1, 0);
	X.resize(2*n, 0); Y.resize(2*n, 0); 
	ll k = 64 - __builtin_clzll(n);
	fir = cnt+1;
	for (ll i=0; i<=M; ++i) C[i] = -fir-1;
	vector<pii> order = dfs(k, n+1);
	sort(all(order), compare);
	A.pb(0);
	for (ll i=0; i<n+1; ++i)
	{
		ll key = order[i].f.f, side = order[i].f.s;
		if (side) X[key] = A[i];
		else Y[key] = A[i];
	}
	X.resize(cnt+1); Y.resize(cnt+1);
	answer(C, X, Y);
	
}

Compilation message

doll.cpp: In function 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> > dfs(ll, ll)':
doll.cpp:64:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |  for (ll i=0; i<le.size(); ++i) le[i].s = le[i].s*2 - 1;
      |               ~^~~~~~~~~~
doll.cpp:65:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  for (ll i=0; i<ri.size(); ++i) ri[i].s = ri[i].s*2;
      |               ~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 37 ms 5972 KB Output is correct
3 Correct 29 ms 5708 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 10 ms 1628 KB Output is correct
6 Correct 46 ms 9948 KB Output is correct
7 Correct 1 ms 348 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 37 ms 5972 KB Output is correct
3 Correct 29 ms 5708 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 10 ms 1628 KB Output is correct
6 Correct 46 ms 9948 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 82 ms 11024 KB Output is correct
9 Correct 64 ms 11036 KB Output is correct
10 Correct 111 ms 19180 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 37 ms 5972 KB Output is correct
3 Correct 29 ms 5708 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 10 ms 1628 KB Output is correct
6 Correct 46 ms 9948 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 82 ms 11024 KB Output is correct
9 Correct 64 ms 11036 KB Output is correct
10 Correct 111 ms 19180 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 99 ms 18960 KB Output is correct
15 Correct 68 ms 10732 KB Output is correct
16 Correct 93 ms 19108 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 93 ms 19196 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 444 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 700 KB Output is correct
2 Correct 54 ms 10516 KB Output is correct
3 Correct 75 ms 10740 KB Output is correct
4 Correct 85 ms 18756 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 700 KB Output is correct
2 Correct 54 ms 10516 KB Output is correct
3 Correct 75 ms 10740 KB Output is correct
4 Correct 85 ms 18756 KB Output is correct
5 Correct 93 ms 18884 KB Output is correct
6 Correct 95 ms 18956 KB Output is correct
7 Correct 98 ms 18816 KB Output is correct
8 Correct 114 ms 18908 KB Output is correct
9 Correct 60 ms 10532 KB Output is correct
10 Correct 81 ms 18796 KB Output is correct
11 Correct 88 ms 18808 KB Output is correct
12 Correct 70 ms 10624 KB Output is correct
13 Correct 86 ms 10776 KB Output is correct
14 Correct 64 ms 10684 KB Output is correct
15 Correct 61 ms 10692 KB Output is correct
16 Correct 2 ms 716 KB Output is correct
17 Correct 58 ms 10532 KB Output is correct
18 Correct 62 ms 10568 KB Output is correct
19 Correct 58 ms 10772 KB Output is correct
20 Correct 82 ms 18708 KB Output is correct
21 Correct 105 ms 18804 KB Output is correct
22 Correct 95 ms 18800 KB Output is correct