oj.uz

Submission #1071683

# Submission time Handle Problem Language Result Execution time Memory
1071683 2024-08-23T09:59:14 Z pan Mechanical Doll (IOI18_doll) C++17
85.553 / 100
 96 ms 20400 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 build(ll idx)
{
	if (pos[idx].size()<=1)
	{
		C[idx] = (pos[idx].size()?pos[idx][0]:0);
		return;
	}
	ll k = 64 - __builtin_clzll(pos[idx].size()-1);
	fir = cnt+1;
	C[idx] = -fir-1;
	vector<pii> order = dfs(k, pos[idx].size());
	sort(all(order), compare);
	for (ll i=0; i<pos[idx].size(); ++i)
	{
		ll key = order[i].f.f, side = order[i].f.s;
		if (side) X[key] = pos[idx][i];
		else Y[key] = pos[idx][i];
	}
	
}
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); 
	a.resize(n);
	for (ll i=0; i<n; ++i) a[i] = A[i];
	pos[0].pb(a[0]);
	for (ll i=0; i<n-1; ++i) pos[A[i]].pb(A[i+1]);
	pos[A[n-1]].pb(0);
	for (ll i=0; i<=M; ++i) build(i);
	X.resize(cnt+1); Y.resize(cnt+1);
	answer(C, X, Y);
	//show(1);
	//for (ll u: C) show(u);
	//show(2);
	//for (ll u: X)  show(u);
	//show(3);
	//for (ll u: Y) show(u);
}

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;
      |               ~^~~~~~~~~~
doll.cpp: In function 'void build(ll)':
doll.cpp:84:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |  for (ll i=0; i<pos[idx].size(); ++i)
      |               ~^~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 26 ms 11832 KB Output is correct
3 Correct 20 ms 9064 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 12 ms 7852 KB Output is correct
6 Correct 32 ms 13884 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 1 ms 348 KB Output is correct
2 Correct 26 ms 11832 KB Output is correct
3 Correct 20 ms 9064 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 12 ms 7852 KB Output is correct
6 Correct 32 ms 13884 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 42 ms 12640 KB Output is correct
9 Correct 44 ms 15552 KB Output is correct
10 Correct 76 ms 19636 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 26 ms 11832 KB Output is correct
3 Correct 20 ms 9064 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 12 ms 7852 KB Output is correct
6 Correct 32 ms 13884 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 42 ms 12640 KB Output is correct
9 Correct 44 ms 15552 KB Output is correct
10 Correct 76 ms 19636 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 78 ms 19480 KB Output is correct
15 Correct 45 ms 10416 KB Output is correct
16 Correct 72 ms 16012 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 76 ms 18472 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 1 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 444 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 344 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 51 ms 11872 KB Output is correct
3 Correct 56 ms 11880 KB Output is correct
4 Correct 90 ms 20400 KB Output is correct

Subtask #6
41.5530038336 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 51 ms 11872 KB Output is correct
3 Correct 56 ms 11880 KB Output is correct
4 Correct 90 ms 20400 KB Output is correct
5 Partially correct 72 ms 18368 KB Output is partially correct
6 Partially correct 70 ms 16936 KB Output is partially correct
7 Partially correct 72 ms 17708 KB Output is partially correct
8 Partially correct 67 ms 15636 KB Output is partially correct
9 Partially correct 52 ms 9988 KB Output is partially correct
10 Partially correct 82 ms 14892 KB Output is partially correct
11 Partially correct 60 ms 13392 KB Output is partially correct
12 Partially correct 38 ms 9048 KB Output is partially correct
13 Partially correct 48 ms 11108 KB Output is partially correct
14 Partially correct 49 ms 11372 KB Output is partially correct
15 Partially correct 51 ms 12248 KB Output is partially correct
16 Partially correct 2 ms 604 KB Output is partially correct
17 Partially correct 37 ms 8588 KB Output is partially correct
18 Partially correct 41 ms 8536 KB Output is partially correct
19 Partially correct 42 ms 8528 KB Output is partially correct
20 Partially correct 59 ms 12796 KB Output is partially correct
21 Partially correct 96 ms 12856 KB Output is partially correct
22 Partially correct 65 ms 12144 KB Output is partially correct