QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#712719#9519. Build a ComputerWillisAC ✓1ms3968kbC++205.1kb2024-11-05 16:46:112024-11-05 16:46:15

Judging History

This is the latest submission verdict.

  • [2024-11-05 16:46:15]
  • Judged
  • Verdict: AC
  • Time: 1ms
  • Memory: 3968kb
  • [2024-11-05 16:46:11]
  • Submitted

answer

#ifdef local
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#endif
// #pragma comment(linker, "/STACK:102400000,102400000")

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

#ifndef local
#define endl '\n'
#endif

#define pb emplace_back
#define fi first
#define se second
#define rep(i, l, r) for (long long i = l; i <= r; i++)
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, x) memset(a, x, sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef double db;
typedef pair<ll, ll> P;
typedef pair<P, ll> PP;
const double pi = acos(-1);
typedef __int128_t int128;
const db eps = 1e-9;
std::mt19937_64 rng(time(0));
ll my_random(ll l, ll r)
{

	uniform_int_distribution<int> range(l, r);
	return range(rng);
}
void __()
{
#ifdef local
	system("pause");
#endif
}
ll qp(ll a, ll b, ll mod)
{
	ll ans = 1;
	while (b)
	{
		if (b & 1)
			ans = ans * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ans;
}

const int maxn = 1e5 + 10;
const ll mod = 998244353;

int trie[110][2];
set<P> val[110];
int nodenum = 1;
vector<P> edge[110];
int endpos;
void insert(vector<int> s, int v)
{
	int len = s.size();
	int st = 1;
	if (s.size() == 1)
	{
		val[1].insert(P{s[0], v});
	}
	else

		for (int i = 0; i < len - 1; i++)
		{
			if (trie[st][s[i]] == 0)
				trie[st][s[i]] = ++nodenum;
			st = trie[st][s[i]];
			if (i == len - 2)
			{
				// cout << st << endl;
				val[st].insert(P{s[len - 1], v});
			}
		}
}
void dfs(int i)
{
	// cout << "YY " << i << endl;
	for (int j = 0; j <= 1; j++)
	{
		if (trie[i][j] != 0)
		{
			dfs(trie[i][j]);
			edge[i].pb(P{trie[i][j], j});
		}
	}
	if (val[i].size() != 0)
	{
		// cout << "XX " << i << endl;
		for (auto x : val[i])
			edge[i].pb(P{endpos - x.se, x.fi});
	}
}

struct node
{
	vector<int> l, r;
	node() {};
	node(vector<int> _l, vector<int> _r) { l = _l, r = _r; };
};
vector<node> vec;
void wk(vector<int> bitl, vector<int> bitr)
{
	int start = bitl.size() - 1;
	for (int i = 0; i < bitl.size() - 1; i++)
	{
		if (bitl[i] != bitr[i])
		{
			start = i;
			break;
		}
	}
	if (bitl[bitl.size() - 1] == 0)
	{
		vector<int> vec2 = bitl;
		vec2[bitl.size() - 1] = 1;
		vec.pb(node(bitl, vec2));
	}
	else
	{
		vec.pb(node(bitl, bitl));
	}
	for (int i = bitl.size() - 2; i > start; i--)
	{
		if (bitl[i] == 0)
		{
			vector<int> b2 = bitl;
			b2[i] = 1;
			for (int j = i + 1; j < b2.size(); j++)
				b2[j] = 0;

			vector<int> b3 = b2;
			for (int j = i + 1; j < b3.size(); j++)
				b3[j] = 1;
			vec.pb(node(b2, b3));
			bitl = b3;
		}
	}
	vector<int> l1 = bitr;
	for (int i = start + 1; i < bitr.size(); i++)
		l1[i] = 0;
	for (int i = start + 1; i < bitr.size() - 1; i++)
	{
		if (bitr[i] == 1)
		{
			vector<int> b2 = bitr;
			b2[i] = 0;
			for (int j = i + 1; j < b2.size(); j++)
				b2[j] = 1;
			vec.pb(node(l1, b2));

			vector<int> b3 = bitr;
			for (int j = i + 1; j < b3.size(); j++)
				b3[j] = 0;
			l1 = b3;
		}
	}
	vec.pb(node(l1, bitr));
}
int main()
{
	IOS;
	int l, r;
	cin >> l >> r;
	vector<int> bitl, bitr;
	int bl = 0, br = 0;
	int l2 = l, r2 = r;
	while (l)
		bitl.pb(l % 2), bl++, l >>= 1;
	while (r)
		bitr.pb(r % 2), br++, r >>= 1;
	for (int i = bl + 1; i <= br; i++)
		bitl.pb(0);
	reverse(bitl.begin(), bitl.end());
	reverse(bitr.begin(), bitr.end());
	if (l2 == r2)
		vec.pb(node(bitl, bitr));
	else if (r2 - l2 == 1 && l2 % 2 == 0)
		vec.pb(node{bitl, bitr});
	else
		wk(bitl, bitr);
	int mxsuf = 0;
	// for (auto x : vec)
	// {
	// 	for (auto u : x.l)
	// 		cout << u;
	// 	cout << " ";
	// 	for (auto u : x.r)
	// 		cout << u;
	// 	cout << endl;
	// }
	for (auto x : vec)
	{
		int n = x.l.size();
		vector<int> common;
		int need = 0;

		bool flag = 0;
		for (int i = 0; i < n; i++)
			if (x.l[i] == x.r[i])
			{
				if (x.l[i] == 1)
					flag = 1;
				if (flag)
					common.pb(x.l[i]);
			}
			else
			{
				need = n - i;
				break;
			}

		insert(common, need);
		// for (auto x : common)
		// 	cout << x;
		// cout << " ";
		// cout << "XX " << need << endl;
		mxsuf = max(mxsuf, need);
	}
	for (int i = 1; i <= mxsuf; i++)
		edge[nodenum + i].pb(P{nodenum + i + 1, 0}), edge[nodenum + i].pb(P{nodenum + i + 1, 1});
	endpos = nodenum + mxsuf + 1;
	dfs(1);
	// cout << nodenum << " " << endpos << endl;
	// for (int i = 1; i < nodenum; i++)
	//{
	//	cout << trie[i][0] << " " << trie[i][1] << endl;
	// }
	cout << endpos << endl;
	for (int i = 1; i <= endpos; i++)
	{
		cout << edge[i].size() << " ";
		for (auto x : edge[i])
			cout << x.fi << " " << x.se << " ";
		cout << endl;
	}
	__();
	return 0;
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3644kb

input:

5 7

output:

5
1 2 1 
2 3 0 4 1 
1 5 1 
2 5 0 5 1 
0 

result:

ok ok

Test #2:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

10 27

output:

9
1 2 1 
4 3 0 4 1 6 0 7 1 
1 8 1 
1 5 0 
2 8 0 8 1 
2 7 0 7 1 
2 8 0 8 1 
2 9 0 9 1 
0 

result:

ok ok

Test #3:

score: 0
Accepted
time: 0ms
memory: 3692kb

input:

5 13

output:

7
1 2 1 
4 3 0 4 1 5 0 6 1 
1 7 1 
1 6 0 
2 6 0 6 1 
2 7 0 7 1 
0 

result:

ok ok

Test #4:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

1 1000000

output:

39
20 2 1 39 1 38 1 37 1 36 1 35 1 34 1 33 1 32 1 31 1 30 1 29 1 28 1 27 1 26 1 25 1 24 1 23 1 22 1 21 1 
2 3 1 21 0 
2 4 1 22 0 
2 5 1 23 0 
1 6 0 
2 7 1 25 0 
1 8 0 
1 9 0 
1 10 0 
1 11 0 
2 12 1 30 0 
1 13 0 
1 14 0 
2 15 1 33 0 
1 16 0 
1 17 0 
1 18 0 
1 19 0 
1 20 0 
1 39 0 
2 22 0 22 1 
2 23 0...

result:

ok ok

Test #5:

score: 0
Accepted
time: 0ms
memory: 3932kb

input:

1 1

output:

2
1 2 1 
0 

result:

ok ok

Test #6:

score: 0
Accepted
time: 0ms
memory: 3696kb

input:

7 9

output:

6
1 2 1 
2 4 0 3 1 
1 6 1 
1 5 0 
2 6 0 6 1 
0 

result:

ok ok

Test #7:

score: 0
Accepted
time: 0ms
memory: 3696kb

input:

3 7

output:

4
1 2 1 
3 3 0 4 1 3 1 
2 4 0 4 1 
0 

result:

ok ok

Test #8:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

1 5

output:

4
3 2 1 4 1 3 1 
1 3 0 
2 4 0 4 1 
0 

result:

ok ok

Test #9:

score: 0
Accepted
time: 0ms
memory: 3924kb

input:

1 4

output:

5
3 2 1 5 1 4 1 
1 3 0 
1 5 0 
2 5 0 5 1 
0 

result:

ok ok

Test #10:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

8 9

output:

5
1 2 1 
1 3 0 
1 4 0 
2 5 0 5 1 
0 

result:

ok ok

Test #11:

score: 0
Accepted
time: 0ms
memory: 3696kb

input:

7 51

output:

10
3 2 1 7 1 6 1 
2 3 1 6 0 
2 4 0 10 1 
1 5 0 
2 9 0 9 1 
2 7 0 7 1 
2 8 0 8 1 
2 9 0 9 1 
2 10 0 10 1 
0 

result:

ok ok

Test #12:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

51 79

output:

14
1 2 1 
2 7 0 3 1 
2 4 0 11 1 
2 5 0 12 1 
1 6 1 
1 14 1 
1 8 0 
2 9 1 11 0 
2 10 1 12 0 
2 13 0 13 1 
2 12 0 12 1 
2 13 0 13 1 
2 14 0 14 1 
0 

result:

ok ok

Test #13:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

92 99

output:

12
1 2 1 
2 3 0 7 1 
1 4 1 
1 5 1 
1 6 1 
2 11 0 11 1 
1 8 0 
1 9 0 
1 10 0 
2 11 0 11 1 
2 12 0 12 1 
0 

result:

ok ok

Test #14:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

27 36

output:

12
1 2 1 
2 6 0 3 1 
2 4 0 10 1 
1 5 1 
1 12 1 
1 7 0 
2 8 1 10 0 
1 9 0 
1 12 0 
2 11 0 11 1 
2 12 0 12 1 
0 

result:

ok ok

Test #15:

score: 0
Accepted
time: 0ms
memory: 3708kb

input:

55 84

output:

16
1 2 1 
2 7 0 3 1 
2 4 0 13 1 
1 5 1 
1 6 1 
1 16 1 
2 8 1 12 0 
1 9 0 
2 10 1 14 0 
1 11 0 
1 16 0 
2 13 0 13 1 
2 14 0 14 1 
2 15 0 15 1 
2 16 0 16 1 
0 

result:

ok ok

Test #16:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

297208 929600

output:

55
1 2 1 
4 3 0 19 1 37 0 38 1 
2 4 0 39 1 
1 5 1 
2 6 0 41 1 
2 7 0 42 1 
2 8 0 43 1 
1 9 1 
2 10 0 45 1 
2 11 0 46 1 
2 12 0 47 1 
1 13 1 
1 14 1 
1 15 1 
1 16 1 
1 17 1 
2 18 0 53 1 
2 54 0 54 1 
2 20 1 38 0 
1 21 0 
1 22 0 
1 23 0 
2 24 1 42 0 
1 25 0 
2 26 1 44 0 
2 27 1 45 0 
2 28 1 46 0 
2 29...

result:

ok ok

Test #17:

score: 0
Accepted
time: 0ms
memory: 3696kb

input:

45728 589156

output:

51
4 2 1 35 1 34 1 33 1 
2 3 0 37 1 
2 16 0 4 1 
1 5 1 
2 6 0 40 1 
2 7 0 41 1 
1 8 1 
2 9 0 43 1 
1 10 1 
2 11 0 45 1 
1 12 1 
2 13 0 47 1 
2 14 0 48 1 
2 15 0 49 1 
2 50 0 50 1 
1 17 0 
2 18 1 36 0 
2 19 1 37 0 
2 20 1 38 0 
2 21 1 39 0 
2 22 1 40 0 
2 23 1 41 0 
1 24 0 
2 25 1 43 0 
1 26 0 
2 27 ...

result:

ok ok

Test #18:

score: 0
Accepted
time: 0ms
memory: 3928kb

input:

129152 138000

output:

45
1 2 1 
2 17 0 3 1 
1 4 1 
1 5 1 
1 6 1 
1 7 1 
2 8 0 35 1 
2 9 0 36 1 
2 10 0 37 1 
1 11 1 
2 12 0 39 1 
2 13 0 40 1 
2 14 0 41 1 
2 15 0 42 1 
2 16 0 43 1 
2 44 0 44 1 
1 18 0 
1 19 0 
1 20 0 
2 21 1 33 0 
2 22 1 34 0 
1 23 0 
2 24 1 36 0 
2 25 1 37 0 
1 26 0 
1 27 0 
1 28 0 
2 29 1 41 0 
1 30 0...

result:

ok ok

Test #19:

score: 0
Accepted
time: 0ms
memory: 3704kb

input:

245280 654141

output:

53
2 2 1 35 1 
2 18 0 3 1 
1 4 1 
2 5 0 39 1 
1 6 1 
1 7 1 
1 8 1 
1 9 1 
1 10 1 
2 11 0 45 1 
2 12 0 46 1 
2 13 0 47 1 
1 14 1 
2 15 0 49 1 
2 16 0 50 1 
2 17 0 51 1 
2 52 0 52 1 
1 19 0 
2 20 1 37 0 
2 21 1 38 0 
2 22 1 39 0 
2 23 1 40 0 
2 24 1 41 0 
2 25 1 42 0 
1 26 0 
2 27 1 44 0 
2 28 1 45 0 ...

result:

ok ok

Test #20:

score: 0
Accepted
time: 0ms
memory: 3968kb

input:

202985 296000

output:

51
1 2 1 
2 19 0 3 1 
2 4 0 36 1 
2 5 0 37 1 
2 6 0 38 1 
1 7 1 
1 8 1 
2 9 0 41 1 
2 10 0 42 1 
2 11 0 43 1 
1 12 1 
1 13 1 
1 14 1 
2 15 0 47 1 
1 16 1 
2 17 0 49 1 
2 18 0 50 1 
1 51 1 
1 20 0 
2 21 1 36 0 
1 22 0 
1 23 0 
1 24 0 
1 25 0 
2 26 1 41 0 
1 27 0 
1 28 0 
1 29 0 
2 30 1 45 0 
1 31 0 
...

result:

ok ok

Test #21:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

438671 951305

output:

54
1 2 1 
2 3 1 36 0 
4 4 0 20 1 37 0 38 1 
1 5 1 
2 6 0 40 1 
1 7 1 
1 8 1 
2 9 0 43 1 
2 10 0 44 1 
2 11 0 45 1 
1 12 1 
1 13 1 
2 14 0 48 1 
2 15 0 49 1 
2 16 0 50 1 
1 17 1 
1 18 1 
1 19 1 
1 54 1 
1 21 0 
2 22 1 39 0 
1 23 0 
1 24 0 
1 25 0 
1 26 0 
2 27 1 44 0 
1 28 0 
1 29 0 
1 30 0 
1 31 0 
...

result:

ok ok

Test #22:

score: 0
Accepted
time: 0ms
memory: 3672kb

input:

425249 739633

output:

54
1 2 1 
2 20 0 3 1 
2 4 0 38 1 
2 5 0 39 1 
1 6 1 
1 7 1 
1 8 1 
1 9 1 
1 10 1 
2 11 0 45 1 
1 12 1 
2 13 0 47 1 
2 14 0 48 1 
1 15 1 
2 16 0 50 1 
2 17 0 51 1 
2 18 0 52 1 
2 19 0 53 1 
1 54 1 
2 21 1 37 0 
2 22 1 38 0 
1 23 0 
2 24 1 40 0 
1 25 0 
1 26 0 
2 27 1 43 0 
1 28 0 
1 29 0 
2 30 1 46 0...

result:

ok ok

Test #23:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

551207 961718

output:

56
1 2 1 
2 3 0 21 1 
2 4 0 39 1 
2 5 0 40 1 
2 6 0 41 1 
1 7 1 
1 8 1 
2 9 0 44 1 
1 10 1 
2 11 0 46 1 
2 12 0 47 1 
1 13 1 
2 14 0 49 1 
2 15 0 50 1 
1 16 1 
2 17 0 52 1 
2 18 0 53 1 
1 19 1 
1 20 1 
1 56 1 
2 22 1 39 0 
1 23 0 
2 24 1 41 0 
1 25 0 
2 26 1 43 0 
1 27 0 
2 28 1 45 0 
2 29 1 46 0 
1...

result:

ok ok

Test #24:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

114691 598186

output:

54
3 2 1 37 1 36 1 
2 18 0 3 1 
1 4 1 
2 5 0 41 1 
2 6 0 42 1 
2 7 0 43 1 
2 8 0 44 1 
2 9 0 45 1 
2 10 0 46 1 
2 11 0 47 1 
2 12 0 48 1 
2 13 0 49 1 
2 14 0 50 1 
2 15 0 51 1 
2 16 0 52 1 
1 17 1 
1 54 1 
1 19 0 
2 20 1 38 0 
1 21 0 
1 22 0 
2 23 1 41 0 
1 24 0 
1 25 0 
1 26 0 
1 27 0 
1 28 0 
2 29...

result:

ok ok

Test #25:

score: 0
Accepted
time: 0ms
memory: 3704kb

input:

234654 253129

output:

44
1 2 1 
1 3 1 
1 4 1 
2 5 0 18 1 
2 6 0 31 1 
1 7 1 
2 8 0 33 1 
1 9 1 
2 10 0 35 1 
2 11 0 36 1 
1 12 1 
2 13 0 38 1 
2 14 0 39 1 
1 15 1 
1 16 1 
1 17 1 
1 43 1 
1 19 0 
2 20 1 32 0 
2 21 1 33 0 
2 22 1 34 0 
1 23 0 
1 24 0 
2 25 1 37 0 
2 26 1 38 0 
1 27 0 
1 28 0 
2 29 1 41 0 
1 30 0 
1 43 0 
...

result:

ok ok

Test #26:

score: 0
Accepted
time: 0ms
memory: 3700kb

input:

554090 608599

output:

50
1 2 1 
1 3 0 
1 4 0 
2 5 0 20 1 
2 6 0 35 1 
1 7 1 
1 8 1 
1 9 1 
2 10 0 39 1 
1 11 1 
2 12 0 41 1 
2 13 0 42 1 
2 14 0 43 1 
1 15 1 
1 16 1 
2 17 0 46 1 
1 18 1 
2 19 0 48 1 
1 49 1 
1 21 0 
2 22 1 36 0 
1 23 0 
1 24 0 
2 25 1 39 0 
1 26 0 
1 27 0 
2 28 1 42 0 
1 29 0 
2 30 1 44 0 
1 31 0 
2 32 ...

result:

ok ok

Extra Test:

score: 0
Extra Test Passed