oj.uz

Submission #879777

# Submission time Handle Problem Language Result Execution time Memory
879777 2023-11-28T05:57:03 Z KiaRez Nice sequence (IZhO18_sequence) C++17
76 / 100
 2000 ms 55008 KB 
/*
    IN THE NAME OF GOD
*/
#include <bits/stdc++.h>

// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;

#define F                                      first
#define S                                      second
#define Mp                                     make_pair
#define pb                                     push_back
#define pf                                     push_front
#define size(x)                                ((ll)x.size())
#define all(x)                                 (x).begin(),(x).end()
#define kill(x)		                           cout << x << '\n', exit(0);
#define fuck(x)                                cout << "(" << #x << " , " << x << ")" << endl
#define endl                                   '\n'

const int N = 1e6+23, lg = 18;
ll Mod = 1e9+7; //998244353;

inline ll MOD(ll a, ll mod=Mod) {a%=mod; (a<0)&&(a+=mod); return a;}
inline ll poww(ll a, ll b, ll mod=Mod) {
    ll ans = 1;
    a=MOD(a, mod);
    while (b) {
        if (b & 1) ans = MOD(ans*a, mod);
        b >>= 1;
        a = MOD(a*a, mod);
    }
    return ans;
}

int t, n, m, deg[N], ord[N];
vector<int> adj[N];

bool check(int mid) {
	for(int i=1; i<=mid; i++) {
		if(i>=m) {
			adj[i-m].pb(i); deg[i]++;
		} 
		if(i>=n) {
			adj[i].pb(i-n); deg[i-n]++;
		}
	}

	queue<int> q;
	for(int i=0; i<=mid; i++) {
		if(deg[i] == 0) q.push(i);
	}
	int cnt = 0; 
	while(size(q) > 0) {
		int v = q.front();
		q.pop();
		ord[v] = cnt++;
		for(int u : adj[v]) {
			deg[u] --;
			if(deg[u] == 0) q.push(u);
		}
	}
	fill(deg, deg+mid+2, 0);
	for(int i=0; i<=mid; i++) adj[i].clear();

	if(cnt == mid+1) return 1;
	return 0;
}

void solve() {
	cin>>n>>m;
	int l=0, r=2*n+2*m+1;
	while(r-l > 1) {
		int mid = (l+r)/2;
		if(check(mid)) l = mid;
		else r = mid;
	}
	check(l);
	cout<<l<<endl;
	for(int i=1; i<=l; i++) {
		ord[i] -= ord[0];
		cout<<(i==1?ord[i]:ord[i]-ord[i-1])<<' ';
	}
	cout<<endl;
}

int main () {
	ios_base::sync_with_stdio(false), cin.tie(0);

	cin>>t;
	while(t--) {
		solve();
	}

	return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27224 KB Ok
2 Correct 6 ms 27228 KB Ok
3 Correct 6 ms 27224 KB Ok
4 Correct 6 ms 27224 KB Ok
5 Correct 6 ms 27228 KB Ok
6 Correct 6 ms 27228 KB Ok
7 Correct 6 ms 27228 KB Ok
8 Correct 6 ms 27256 KB Ok
9 Correct 6 ms 27228 KB Ok
10 Correct 6 ms 27228 KB Ok
11 Correct 7 ms 27228 KB Ok
12 Correct 6 ms 27228 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27224 KB Ok
2 Correct 7 ms 27228 KB Ok
3 Correct 7 ms 27228 KB Ok
4 Correct 5 ms 27228 KB Ok
5 Correct 6 ms 27272 KB Ok
6 Correct 9 ms 27228 KB Ok
7 Correct 23 ms 27740 KB Ok
8 Correct 13 ms 27480 KB Ok
9 Correct 25 ms 27984 KB Ok
10 Correct 16 ms 27484 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 27228 KB Ok
2 Correct 5 ms 27228 KB Ok
3 Correct 6 ms 27252 KB Ok
4 Correct 6 ms 27228 KB Ok
5 Correct 6 ms 27316 KB Ok
6 Correct 6 ms 27228 KB Ok
7 Correct 6 ms 27228 KB Ok
8 Correct 6 ms 27316 KB Ok
9 Correct 6 ms 27228 KB Ok
10 Correct 6 ms 27228 KB Ok
11 Correct 5 ms 27228 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27224 KB Ok
2 Correct 5 ms 27228 KB Ok
3 Correct 6 ms 27228 KB Ok
4 Correct 5 ms 27228 KB Ok
5 Correct 5 ms 27228 KB Ok
6 Correct 214 ms 35296 KB Ok
7 Correct 203 ms 35540 KB Ok
8 Correct 385 ms 37696 KB Ok
9 Correct 261 ms 37272 KB Ok
10 Correct 165 ms 32568 KB Ok
11 Correct 261 ms 36916 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27224 KB Ok
2 Correct 6 ms 27228 KB Ok
3 Correct 6 ms 27224 KB Ok
4 Correct 6 ms 27224 KB Ok
5 Correct 6 ms 27228 KB Ok
6 Correct 6 ms 27228 KB Ok
7 Correct 6 ms 27228 KB Ok
8 Correct 6 ms 27256 KB Ok
9 Correct 6 ms 27228 KB Ok
10 Correct 6 ms 27228 KB Ok
11 Correct 7 ms 27228 KB Ok
12 Correct 6 ms 27228 KB Ok
13 Correct 6 ms 27228 KB Ok
14 Correct 5 ms 27228 KB Ok
15 Correct 6 ms 27252 KB Ok
16 Correct 6 ms 27228 KB Ok
17 Correct 6 ms 27316 KB Ok
18 Correct 6 ms 27228 KB Ok
19 Correct 6 ms 27228 KB Ok
20 Correct 6 ms 27316 KB Ok
21 Correct 6 ms 27228 KB Ok
22 Correct 6 ms 27228 KB Ok
23 Correct 5 ms 27228 KB Ok
24 Correct 9 ms 27228 KB Ok
25 Correct 9 ms 27224 KB Ok
26 Correct 9 ms 27228 KB Ok
27 Correct 8 ms 27228 KB Ok
28 Correct 8 ms 27224 KB Ok
29 Correct 8 ms 27228 KB Ok
30 Correct 8 ms 27228 KB Ok
31 Correct 11 ms 27228 KB Ok
32 Correct 9 ms 27228 KB Ok
33 Correct 8 ms 27224 KB Ok
34 Correct 12 ms 27484 KB Ok
35 Correct 12 ms 27484 KB Ok
36 Correct 12 ms 27480 KB Ok
37 Correct 13 ms 27484 KB Ok
38 Correct 12 ms 27484 KB Ok
39 Correct 12 ms 27480 KB Ok
40 Correct 13 ms 27484 KB Ok
41 Correct 13 ms 27504 KB Ok
42 Correct 12 ms 27484 KB Ok
43 Correct 12 ms 27516 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27224 KB Ok
2 Correct 6 ms 27228 KB Ok
3 Correct 6 ms 27224 KB Ok
4 Correct 6 ms 27224 KB Ok
5 Correct 6 ms 27228 KB Ok
6 Correct 6 ms 27228 KB Ok
7 Correct 6 ms 27228 KB Ok
8 Correct 6 ms 27256 KB Ok
9 Correct 6 ms 27228 KB Ok
10 Correct 6 ms 27228 KB Ok
11 Correct 7 ms 27228 KB Ok
12 Correct 6 ms 27228 KB Ok
13 Correct 5 ms 27224 KB Ok
14 Correct 7 ms 27228 KB Ok
15 Correct 7 ms 27228 KB Ok
16 Correct 5 ms 27228 KB Ok
17 Correct 6 ms 27272 KB Ok
18 Correct 9 ms 27228 KB Ok
19 Correct 23 ms 27740 KB Ok
20 Correct 13 ms 27480 KB Ok
21 Correct 25 ms 27984 KB Ok
22 Correct 16 ms 27484 KB Ok
23 Correct 6 ms 27228 KB Ok
24 Correct 5 ms 27228 KB Ok
25 Correct 6 ms 27252 KB Ok
26 Correct 6 ms 27228 KB Ok
27 Correct 6 ms 27316 KB Ok
28 Correct 6 ms 27228 KB Ok
29 Correct 6 ms 27228 KB Ok
30 Correct 6 ms 27316 KB Ok
31 Correct 6 ms 27228 KB Ok
32 Correct 6 ms 27228 KB Ok
33 Correct 5 ms 27228 KB Ok
34 Correct 9 ms 27228 KB Ok
35 Correct 9 ms 27224 KB Ok
36 Correct 9 ms 27228 KB Ok
37 Correct 8 ms 27228 KB Ok
38 Correct 8 ms 27224 KB Ok
39 Correct 8 ms 27228 KB Ok
40 Correct 8 ms 27228 KB Ok
41 Correct 11 ms 27228 KB Ok
42 Correct 9 ms 27228 KB Ok
43 Correct 8 ms 27224 KB Ok
44 Correct 12 ms 27484 KB Ok
45 Correct 12 ms 27484 KB Ok
46 Correct 12 ms 27480 KB Ok
47 Correct 13 ms 27484 KB Ok
48 Correct 12 ms 27484 KB Ok
49 Correct 12 ms 27480 KB Ok
50 Correct 13 ms 27484 KB Ok
51 Correct 13 ms 27504 KB Ok
52 Correct 12 ms 27484 KB Ok
53 Correct 12 ms 27516 KB Ok
54 Correct 158 ms 31572 KB Ok
55 Correct 185 ms 31816 KB Ok
56 Correct 178 ms 32012 KB Ok
57 Correct 137 ms 31324 KB Ok
58 Correct 171 ms 31820 KB Ok
59 Correct 161 ms 31864 KB Ok
60 Correct 141 ms 31556 KB Ok
61 Correct 156 ms 31696 KB Ok
62 Correct 189 ms 31808 KB Ok
63 Correct 149 ms 31448 KB Ok
64 Correct 176 ms 31732 KB Ok
65 Correct 176 ms 31696 KB Ok
66 Correct 165 ms 31652 KB Ok
67 Correct 139 ms 31152 KB Ok
68 Correct 160 ms 31760 KB Ok
69 Correct 304 ms 35852 KB Ok
70 Correct 343 ms 37056 KB Ok
71 Correct 286 ms 35096 KB Ok
72 Correct 304 ms 36084 KB Ok
73 Correct 296 ms 35592 KB Ok
74 Correct 282 ms 34640 KB Ok
75 Correct 296 ms 34604 KB Ok
76 Correct 326 ms 36620 KB Ok
77 Correct 267 ms 34160 KB Ok
78 Correct 341 ms 36628 KB Ok
79 Correct 311 ms 35856 KB Ok
80 Correct 290 ms 35492 KB Ok
81 Correct 307 ms 36060 KB Ok
82 Correct 303 ms 35608 KB Ok
83 Correct 288 ms 35272 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27224 KB Ok
2 Correct 6 ms 27228 KB Ok
3 Correct 6 ms 27224 KB Ok
4 Correct 6 ms 27224 KB Ok
5 Correct 6 ms 27228 KB Ok
6 Correct 6 ms 27228 KB Ok
7 Correct 6 ms 27228 KB Ok
8 Correct 6 ms 27256 KB Ok
9 Correct 6 ms 27228 KB Ok
10 Correct 6 ms 27228 KB Ok
11 Correct 7 ms 27228 KB Ok
12 Correct 6 ms 27228 KB Ok
13 Correct 5 ms 27224 KB Ok
14 Correct 7 ms 27228 KB Ok
15 Correct 7 ms 27228 KB Ok
16 Correct 5 ms 27228 KB Ok
17 Correct 6 ms 27272 KB Ok
18 Correct 9 ms 27228 KB Ok
19 Correct 23 ms 27740 KB Ok
20 Correct 13 ms 27480 KB Ok
21 Correct 25 ms 27984 KB Ok
22 Correct 16 ms 27484 KB Ok
23 Correct 6 ms 27228 KB Ok
24 Correct 5 ms 27228 KB Ok
25 Correct 6 ms 27252 KB Ok
26 Correct 6 ms 27228 KB Ok
27 Correct 6 ms 27316 KB Ok
28 Correct 6 ms 27228 KB Ok
29 Correct 6 ms 27228 KB Ok
30 Correct 6 ms 27316 KB Ok
31 Correct 6 ms 27228 KB Ok
32 Correct 6 ms 27228 KB Ok
33 Correct 5 ms 27228 KB Ok
34 Correct 5 ms 27224 KB Ok
35 Correct 5 ms 27228 KB Ok
36 Correct 6 ms 27228 KB Ok
37 Correct 5 ms 27228 KB Ok
38 Correct 5 ms 27228 KB Ok
39 Correct 214 ms 35296 KB Ok
40 Correct 203 ms 35540 KB Ok
41 Correct 385 ms 37696 KB Ok
42 Correct 261 ms 37272 KB Ok
43 Correct 165 ms 32568 KB Ok
44 Correct 261 ms 36916 KB Ok
45 Correct 9 ms 27228 KB Ok
46 Correct 9 ms 27224 KB Ok
47 Correct 9 ms 27228 KB Ok
48 Correct 8 ms 27228 KB Ok
49 Correct 8 ms 27224 KB Ok
50 Correct 8 ms 27228 KB Ok
51 Correct 8 ms 27228 KB Ok
52 Correct 11 ms 27228 KB Ok
53 Correct 9 ms 27228 KB Ok
54 Correct 8 ms 27224 KB Ok
55 Correct 12 ms 27484 KB Ok
56 Correct 12 ms 27484 KB Ok
57 Correct 12 ms 27480 KB Ok
58 Correct 13 ms 27484 KB Ok
59 Correct 12 ms 27484 KB Ok
60 Correct 12 ms 27480 KB Ok
61 Correct 13 ms 27484 KB Ok
62 Correct 13 ms 27504 KB Ok
63 Correct 12 ms 27484 KB Ok
64 Correct 12 ms 27516 KB Ok
65 Correct 158 ms 31572 KB Ok
66 Correct 185 ms 31816 KB Ok
67 Correct 178 ms 32012 KB Ok
68 Correct 137 ms 31324 KB Ok
69 Correct 171 ms 31820 KB Ok
70 Correct 161 ms 31864 KB Ok
71 Correct 141 ms 31556 KB Ok
72 Correct 156 ms 31696 KB Ok
73 Correct 189 ms 31808 KB Ok
74 Correct 149 ms 31448 KB Ok
75 Correct 176 ms 31732 KB Ok
76 Correct 176 ms 31696 KB Ok
77 Correct 165 ms 31652 KB Ok
78 Correct 139 ms 31152 KB Ok
79 Correct 160 ms 31760 KB Ok
80 Correct 304 ms 35852 KB Ok
81 Correct 343 ms 37056 KB Ok
82 Correct 286 ms 35096 KB Ok
83 Correct 304 ms 36084 KB Ok
84 Correct 296 ms 35592 KB Ok
85 Correct 282 ms 34640 KB Ok
86 Correct 296 ms 34604 KB Ok
87 Correct 326 ms 36620 KB Ok
88 Correct 267 ms 34160 KB Ok
89 Correct 341 ms 36628 KB Ok
90 Correct 311 ms 35856 KB Ok
91 Correct 290 ms 35492 KB Ok
92 Correct 307 ms 36060 KB Ok
93 Correct 303 ms 35608 KB Ok
94 Correct 288 ms 35272 KB Ok
95 Correct 429 ms 40304 KB Ok
96 Correct 669 ms 46360 KB Ok
97 Correct 637 ms 42904 KB Ok
98 Correct 471 ms 41876 KB Ok
99 Correct 562 ms 42172 KB Ok
100 Correct 589 ms 40924 KB Ok
101 Correct 599 ms 46188 KB Ok
102 Correct 578 ms 43556 KB Ok
103 Correct 587 ms 42128 KB Ok
104 Correct 740 ms 46976 KB Ok
105 Correct 655 ms 45520 KB Ok
106 Correct 558 ms 45268 KB Ok
107 Correct 649 ms 43848 KB Ok
108 Correct 717 ms 45684 KB Ok
109 Correct 637 ms 46072 KB Ok
110 Execution timed out 2039 ms 55008 KB Time limit exceeded
111 Halted 0 ms 0 KB -