QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#853081 | #9519. Build a Computer | Rafat_Kabir | AC ✓ | 8ms | 11072kb | C++20 | 5.5kb | 2025-01-11 15:37:15 | 2025-01-11 15:37:16 |
Judging History
answer
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <time.h>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <cstring>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <iostream>
using namespace __gnu_pbds;
using namespace std;
template <class T>
using Tree =
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// to erase in multiset-> less_equal<T> and
// s.erase(s.find_by_order(s.order_of_key(x)))
// lower_bound(x)=>(cannot use the stl lower_bound function)
// ll idx = s.order_of_key(x)
// if(idx == s.size()) -> no lower_bound
// else lb = *s.find_by_order(idx) // as 0-indexing
// idx-1 will give highest value which is strictly less than x
// for upper_bound->do the same with (x+1)
typedef long long ll;
typedef long double ld;
typedef pair<int,int> p32;
typedef pair<ll,ll> p64;
typedef tuple<ll, ll, ll> t64;
typedef vector<t64> vt64;
typedef vector<vt64> vvt64;
typedef pair<double,double> pdd;
typedef vector<ll> v64;
typedef vector<int> v32;
typedef vector<vector<int> > vv32;
typedef vector<vector<ll> > vv64;
typedef vector<vector<p64> > vvp64;
typedef vector<p64> vp64;
typedef vector<p32> vp32;
typedef vector<vector<p32> > vvp32;
typedef vector<bool> vb;
ll mod = 1e9+7, MOD = 998244353;
double eps = 1e-12;
#define FOR(s, e, i) for(ll i = s; i <= e; i++)
#define ROF(s ,e, i) for(ll i = s; i >= e; i--)
#define F0R(i, e) for(ll i = 0; i < (e); i++)
#define trav(e, a) for(auto &e : a)
#define coutAll(A) for(auto asdafas : A) cout << asdafas << " "; cout << "\n";
#define foutAll(A) for(auto asdafas : A) fout << asdafas << " "; cout << "\n";
#define cinAll(A) for(auto &asdafas : A) cin >> asdafas;
#define finAll(A) for(auto &asdafas : A) fin >> asdafas;
#define minpq priority_queue<ll, v64, greater<ll>>
#define maxpq priority_queue<ll>
#define ln "\n"
#define dbg(x) cout<<#x<<" = "<<x<<ln
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define fi first
#define se second
ll inf = LLONG_MAX;
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((ll)(x).size())
#define yes cout<<"yes\n"
#define no cout<<"no\n"
#define Yes cout<<"Yes\n"
#define No cout<<"No\n"
#define YES cout<<"YES\n"
#define NO cout<<"NO\n"
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef pair<ll, ll> pll;
typedef pair<ll, ll> pii;
#define MAXN 100005
void solve(int it)
{
int l, r;
cin >> l >> r;
// 1 er start, 2 e end
// template path
vvp32 adj(MAXN);
FOR(3, 20, i){
// 2 er shathe
// adj[i].emplace_back(2, 0);
// adj[i].emplace_back(2, 1);
// i+1 er shathe
adj[i].emplace_back(i+1, 0);
adj[i].emplace_back(i+1, 1);
}
adj[21].emplace_back(2,0);
adj[21].emplace_back(2,1);
v32 pw(30);
int idx = 1;
pw[0] = 2;
ROF(21, 3, i) pw[idx++] = i;
int cur = 21;
auto rec = [&](auto&&self, v32&a, int startbit, int bit, int last)->void{
if(a.empty()) return;
// cout << bit << "->";
// coutAll(a);
if(sz(a)==(1<<bit)){
// shob ase
adj[last].emplace_back(pw[bit], startbit);
return;
}
// divide in 1s and 0s for next bit
v32 ones, zeros;
trav(e, a){
if((e>>(bit-1))&1) ones.pb(e);
else zeros.pb(e);
}
// 2 branch
// for 0
if(sz(zeros)){
adj[last].emplace_back(++cur, startbit);
self(self, zeros, 0, bit-1, cur);
}
// for 1
if(sz(ones)){
adj[last].emplace_back(++cur, startbit);
self(self, ones, 1, bit-1, cur);
}
};
ROF(19, 0, bit){
v32 a;
while(r >= l && ((r>>bit)&1)){
a.pb(r);
--r;
}
rec(rec, a, 1, bit, 1);
}
queue<int>q;
vb vis(cur+1);
q.push(1);
vis[1] = true;
vvp32 ans(cur+1);
while(!q.empty()){
int u = q.front();
// cout << u << " " << sz(adj[u]) << "\n";
q.pop();
ans[u] = adj[u];
trav(vw, adj[u]){
int v = vw.fi;
// ans[u].pb(vw);
if(!vis[v]){
vis[v] = true;
q.push(v);
}
}
}
// FOR(1, cur, i){
// if()
// }
map<int, int> comp;
FOR(1, cur, i){
if(ans[i].empty()) continue;
// cout << i << "->";
comp[i] = 0;
trav(e, ans[i]){
// cout << e.fi << " " << e.se << " ";
comp[e.fi] = 0;
}
// cout << "\n";
}
int siz = 0;
trav(e, comp) e.se = ++siz;
// trav(e, comp) cout << e.fi << " " << e.se << "\n" ;
// cur = siz;
adj = ans;
cout << siz << "\n";
FOR(1, cur, j){
int i = comp[j];
if(i==0) continue;;
// cout << j << " " << i << "\n";
cout << sz(adj[j]) << " ";
trav(e, adj[j]) cout << comp[e.fi] << " " << e.se << " ";
cout << "\n";
}
}
int main()
{
fast_cin();
ll t = 1;
// cin >> t;
for(int it=1; it<=t; it++)
{
//cout << "Case " << it << ": ";
solve(it);
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5436kb
input:
5 7
output:
6 2 4 1 6 1 0 2 2 0 2 1 1 5 0 1 2 1 1 3 1
result:
ok ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 5596kb
input:
10 27
output:
11 4 6 1 7 1 9 1 11 1 0 2 4 0 4 1 2 5 0 5 1 2 2 0 2 1 1 3 0 1 8 1 1 4 0 1 10 0 1 5 1 1 4 1
result:
ok ok
Test #3:
score: 0
Accepted
time: 1ms
memory: 5432kb
input:
5 13
output:
10 4 5 1 6 1 8 1 10 1 0 2 4 0 4 1 2 2 0 2 1 1 3 0 1 7 1 1 4 0 1 9 0 1 2 1 1 4 1
result:
ok ok
Test #4:
score: 0
Accepted
time: 8ms
memory: 11072kb
input:
1 1000000
output:
45 21 21 1 22 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 2 1 0 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1 2 16 0 16 1 2 17 0 17 1 2 18 0 18 1 2 19 0 19 ...
result:
ok ok
Test #5:
score: 0
Accepted
time: 1ms
memory: 5476kb
input:
1 1
output:
2 1 2 1 0
result:
ok ok
Test #6:
score: 0
Accepted
time: 1ms
memory: 5540kb
input:
7 9
output:
7 2 4 1 6 1 0 2 2 0 2 1 1 5 0 1 3 0 1 7 1 1 2 1
result:
ok ok
Test #7:
score: 0
Accepted
time: 1ms
memory: 5552kb
input:
3 7
output:
5 2 3 1 5 1 0 2 4 0 4 1 2 2 0 2 1 1 2 1
result:
ok ok
Test #8:
score: 0
Accepted
time: 1ms
memory: 5412kb
input:
1 5
output:
4 3 4 1 3 1 2 1 0 2 2 0 2 1 1 3 0
result:
ok ok
Test #9:
score: 0
Accepted
time: 1ms
memory: 5544kb
input:
1 4
output:
5 3 4 1 3 1 2 1 0 2 2 0 2 1 1 5 0 1 2 0
result:
ok ok
Test #10:
score: 0
Accepted
time: 0ms
memory: 5404kb
input:
8 9
output:
5 1 4 1 0 2 2 0 2 1 1 5 0 1 3 0
result:
ok ok
Test #11:
score: 0
Accepted
time: 1ms
memory: 5448kb
input:
7 51
output:
12 5 7 1 8 1 3 1 4 1 11 1 0 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 2 0 2 1 1 3 0 1 9 1 1 10 0 1 5 0 1 12 1 1 2 1
result:
ok ok
Test #12:
score: 0
Accepted
time: 1ms
memory: 5524kb
input:
51 79
output:
15 2 7 1 9 1 0 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 2 0 2 1 1 8 0 1 3 0 2 10 1 15 1 2 11 0 14 0 1 12 0 1 13 1 1 2 1 1 5 1 1 4 1
result:
ok ok
Test #13:
score: 0
Accepted
time: 0ms
memory: 5544kb
input:
92 99
output:
12 2 5 1 9 1 0 2 4 0 4 1 2 2 0 2 1 1 6 0 1 7 1 1 8 1 1 3 1 1 10 1 1 11 0 1 12 0 1 3 0
result:
ok ok
Test #14:
score: 0
Accepted
time: 1ms
memory: 5612kb
input:
27 36
output:
15 2 5 1 11 1 0 2 4 0 4 1 2 2 0 2 1 1 6 0 2 7 0 8 0 1 3 0 1 9 1 1 10 0 1 2 0 2 12 1 15 1 1 13 0 1 14 1 1 2 1 1 3 1
result:
ok ok
Test #15:
score: 0
Accepted
time: 1ms
memory: 5456kb
input:
55 84
output:
20 2 7 1 15 1 0 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 2 0 2 1 2 8 0 9 0 1 3 0 1 10 1 2 11 0 12 0 1 5 0 1 13 1 1 14 0 1 2 0 2 16 1 20 1 1 17 0 1 18 1 1 19 1 1 2 1 1 4 1
result:
ok ok
Test #16:
score: 0
Accepted
time: 4ms
memory: 10284kb
input:
297208 929600
output:
70 4 21 1 22 1 48 1 70 1 0 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1 2 16 0 16 1 2 17 0 17 1 2 18 0 18 1 2 19 0 19 1 2 20 0 20 1 2 2 0 2 1 1 3 0 2 23 1 24 1 1 4 0 1 25 1 1 26 0 1 27 0 ...
result:
ok ok
Test #17:
score: 0
Accepted
time: 5ms
memory: 7048kb
input:
45728 589156
output:
64 6 21 1 3 1 4 1 5 1 50 1 64 1 0 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1 2 16 0 16 1 2 17 0 17 1 2 18 0 18 1 2 19 0 19 1 2 20 0 20 1 2 2 0 2 1 1 22 0 1 23 0 2 24 0 25 0 1 6 0 2 26 1 2...
result:
ok ok
Test #18:
score: 0
Accepted
time: 1ms
memory: 5756kb
input:
129152 138000
output:
48 2 15 1 37 1 0 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 2 0 2 1 1 16 0 1 17 0 1 18 0 2 19 0 20 0 1 3 0 2 21 1 22 1 1 4 0 1 23 1 2 24 0 25 0 1 6 0 2 26 1 27 1 1 7 0 1 28 1 1 29 0 1 30 0 2 3...
result:
ok ok
Test #19:
score: 0
Accepted
time: 5ms
memory: 8236kb
input:
245280 654141
output:
66 3 21 1 3 1 51 1 0 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1 2 16 0 16 1 2 17 0 17 1 2 18 0 18 1 2 19 0 19 1 2 20 0 20 1 2 2 0 2 1 1 22 0 2 23 0 24 0 1 5 0 2 25 1 26 1 1 6 0 2 27 1 28...
result:
ok ok
Test #20:
score: 0
Accepted
time: 2ms
memory: 6384kb
input:
202985 296000
output:
64 2 18 1 39 1 0 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1 2 16 0 16 1 2 17 0 17 1 2 2 0 2 1 1 19 0 2 20 0 21 0 1 3 0 1 22 1 1 23 0 1 24 0 1 25 0 2 26 0 27 0 1 8 0 1 28 1 1 29 0 1 30...
result:
ok ok
Test #21:
score: 0
Accepted
time: 3ms
memory: 10456kb
input:
438671 951305
output:
69 3 21 1 22 1 44 1 0 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1 2 16 0 16 1 2 17 0 17 1 2 18 0 18 1 2 19 0 19 1 2 20 0 20 1 2 2 0 2 1 1 3 0 2 23 1 24 1 1 4 0 1 25 1 2 26 0 27 0 1 6 0 1...
result:
ok ok
Test #22:
score: 0
Accepted
time: 0ms
memory: 8840kb
input:
425249 739633
output:
71 2 20 1 45 1 0 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1 2 16 0 16 1 2 17 0 17 1 2 18 0 18 1 2 19 0 19 1 2 2 0 2 1 2 21 0 22 0 1 3 0 2 23 1 24 1 1 4 0 1 25 1 2 26 0 27 0 1 6 0 1 28 1...
result:
ok ok
Test #23:
score: 0
Accepted
time: 3ms
memory: 10708kb
input:
551207 961718
output:
77 2 20 1 49 1 0 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1 2 16 0 16 1 2 17 0 17 1 2 18 0 18 1 2 19 0 19 1 2 2 0 2 1 2 21 0 48 0 2 22 0 47 0 2 23 0 46 0 1 24 0 1 25 1 2 26 1 45 1 1 27 0...
result:
ok ok
Test #24:
score: 0
Accepted
time: 4ms
memory: 7824kb
input:
114691 598186
output:
73 4 21 1 3 1 4 1 46 1 0 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1 2 16 0 16 1 2 17 0 17 1 2 18 0 18 1 2 19 0 19 1 2 20 0 20 1 2 2 0 2 1 1 22 0 2 23 0 24 0 1 5 0 1 25 1 1 26 0 2 27 0 28...
result:
ok ok
Test #25:
score: 0
Accepted
time: 0ms
memory: 6068kb
input:
234654 253129
output:
57 1 16 1 0 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1 2 2 0 2 1 1 17 1 2 18 1 38 1 2 19 0 37 0 1 20 0 2 21 1 36 1 1 22 0 2 23 1 35 1 2 24 0 34 0 1 25 0 2 26 1 33 1 2 27 0 32 0 1 28 0 ...
result:
ok ok
Test #26:
score: 0
Accepted
time: 2ms
memory: 6752kb
input:
554090 608599
output:
61 1 18 1 0 2 4 0 4 1 2 5 0 5 1 2 6 0 6 1 2 7 0 7 1 2 8 0 8 1 2 9 0 9 1 2 10 0 10 1 2 11 0 11 1 2 12 0 12 1 2 13 0 13 1 2 14 0 14 1 2 15 0 15 1 2 16 0 16 1 2 17 0 17 1 2 2 0 2 1 1 19 0 2 20 0 43 0 2 21 0 42 0 1 22 0 1 23 1 1 24 1 2 25 1 41 1 1 26 0 2 27 1 40 1 2 28 0 39 0 ...
result:
ok ok
Extra Test:
score: 0
Extra Test Passed