oj.uz

Submission #928531

# Submission time Handle Problem Language Result Execution time Memory
928531 2024-02-16T15:13:21 Z pan Handcrafted Gift (IOI20_gift) C++17
100 / 100
 1042 ms 60940 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include "bits_stdc++.h"
#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 discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define auto set<pi>:: iterator 
using namespace std;
//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 long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<ll, pi> pii;
#include <vector>
#include <string>

set<pi> ranges;
vector<pi> condition;
ll const INF = 1e13;
void merge(ll l, ll r)
{
	auto lower = --ranges.ub(mp(l, INF));
	auto upper = --ranges.ub(mp(r, INF));
	l = lower->f; r = upper->s;
	while (lower!=upper) lower = ranges.erase(lower);
	ranges.erase(lower);
	ranges.insert(mp(l, r));
}
void craft(std::string &s);
int construct(int n, int r, std::vector<int> a, std::vector<int> b,  std::vector<int> x)
{
	ranges.clear();
	condition.resize(0);
	for (ll i=0; i<n; ++i) ranges.insert(mp(i,i));
	for (ll i=0; i<r; ++i)
	{
		if (x[i]==1) merge(a[i], b[i]);
		else condition.pb(mp(a[i], b[i]));
	}
	for (ll i=0; i<condition.size(); ++i)
	{
		ll l  = condition[i].f, r = condition[i].s;
		auto lower  = --ranges.ub(mp(l, INF));
		auto upper = --ranges.ub(mp(r, INF));
		if (lower==upper) return 0;
	}
	string ret = "";
	string arr[2] = {"R", "B"};
	ll cycle = 0;
	for (auto it = ranges.begin(); it!=ranges.end(); ++it)
	{
		for (ll u = 0; u<it->s-it->f+1; ++u) ret+=arr[cycle];
		cycle = (1-cycle)%2;
	}
	craft(ret);
	return 1;
}

Compilation message

gift.cpp: In function 'int construct(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
gift.cpp:57:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  for (ll i=0; i<condition.size(); ++i)
      |               ~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 432 KB Output is correct
4 Correct 4 ms 1524 KB Output is correct
5 Correct 302 ms 51584 KB Output is correct
6 Correct 304 ms 51584 KB Output is correct
7 Correct 325 ms 51280 KB Output is correct
8 Correct 310 ms 51332 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 7 ms 1684 KB Output is correct
4 Correct 1042 ms 60420 KB Output is correct
5 Correct 1012 ms 60596 KB Output is correct
6 Correct 448 ms 60940 KB Output is correct
7 Correct 446 ms 59396 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 1 ms 604 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 432 KB Output is correct
4 Correct 4 ms 1524 KB Output is correct
5 Correct 302 ms 51584 KB Output is correct
6 Correct 304 ms 51584 KB Output is correct
7 Correct 325 ms 51280 KB Output is correct
8 Correct 310 ms 51332 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 7 ms 1684 KB Output is correct
12 Correct 1042 ms 60420 KB Output is correct
13 Correct 1012 ms 60596 KB Output is correct
14 Correct 448 ms 60940 KB Output is correct
15 Correct 446 ms 59396 KB Output is correct
16 Correct 0 ms 344 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 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 344 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 1 ms 604 KB Output is correct
30 Correct 2 ms 640 KB Output is correct
31 Correct 1 ms 604 KB Output is correct
32 Correct 1 ms 604 KB Output is correct
33 Correct 1 ms 604 KB Output is correct
34 Correct 2 ms 604 KB Output is correct
35 Correct 109 ms 32104 KB Output is correct
36 Correct 130 ms 32768 KB Output is correct
37 Correct 130 ms 32856 KB Output is correct
38 Correct 551 ms 56836 KB Output is correct
39 Correct 294 ms 56352 KB Output is correct
40 Correct 623 ms 56448 KB Output is correct
41 Correct 769 ms 56528 KB Output is correct
42 Correct 619 ms 56148 KB Output is correct