oj.uz

Submission #879778

# Submission time Handle Problem Language Result Execution time Memory
879778 2023-11-28T06:01:57 Z KiaRez Nice sequence (IZhO18_sequence) C++17
100 / 100
 750 ms 34744 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];

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 i = q.front();
		q.pop();
		ord[i] = cnt++;
		if(i-n>=0) {
			deg[i-n] --;
			if(deg[i-n] == 0) q.push(i-n);
		}
		if(i+m<=mid) {
			deg[i+m] --;
			if(deg[i+m] == 0) q.push(i+m);
		}
	}
	fill(deg, deg+mid+2, 0);

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

void solve() {
	cin>>n>>m;
	int l=0, r=2*(n+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 1 ms 2392 KB Ok
2 Correct 1 ms 2396 KB Ok
3 Correct 1 ms 2396 KB Ok
4 Correct 1 ms 2396 KB Ok
5 Correct 1 ms 2396 KB Ok
6 Correct 1 ms 2396 KB Ok
7 Correct 1 ms 2396 KB Ok
8 Correct 1 ms 2400 KB Ok
9 Correct 1 ms 2396 KB Ok
10 Correct 1 ms 2396 KB Ok
11 Correct 1 ms 2396 KB Ok
12 Correct 1 ms 2396 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Ok
2 Correct 1 ms 2396 KB Ok
3 Correct 1 ms 2396 KB Ok
4 Correct 0 ms 2396 KB Ok
5 Correct 1 ms 2396 KB Ok
6 Correct 3 ms 2520 KB Ok
7 Correct 12 ms 2768 KB Ok
8 Correct 5 ms 2652 KB Ok
9 Correct 15 ms 2932 KB Ok
10 Correct 8 ms 2652 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Ok
2 Correct 1 ms 2396 KB Ok
3 Correct 0 ms 2396 KB Ok
4 Correct 0 ms 2396 KB Ok
5 Correct 0 ms 2508 KB Ok
6 Correct 1 ms 2396 KB Ok
7 Correct 0 ms 2396 KB Ok
8 Correct 1 ms 2512 KB Ok
9 Correct 1 ms 2396 KB Ok
10 Correct 0 ms 2396 KB Ok
11 Correct 1 ms 2396 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2512 KB Ok
2 Correct 1 ms 2396 KB Ok
3 Correct 1 ms 2396 KB Ok
4 Correct 1 ms 2396 KB Ok
5 Correct 1 ms 2396 KB Ok
6 Correct 127 ms 9528 KB Ok
7 Correct 114 ms 8984 KB Ok
8 Correct 231 ms 11224 KB Ok
9 Correct 158 ms 11656 KB Ok
10 Correct 96 ms 8280 KB Ok
11 Correct 162 ms 10368 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Ok
2 Correct 1 ms 2396 KB Ok
3 Correct 1 ms 2396 KB Ok
4 Correct 1 ms 2396 KB Ok
5 Correct 1 ms 2396 KB Ok
6 Correct 1 ms 2396 KB Ok
7 Correct 1 ms 2396 KB Ok
8 Correct 1 ms 2400 KB Ok
9 Correct 1 ms 2396 KB Ok
10 Correct 1 ms 2396 KB Ok
11 Correct 1 ms 2396 KB Ok
12 Correct 1 ms 2396 KB Ok
13 Correct 0 ms 2396 KB Ok
14 Correct 1 ms 2396 KB Ok
15 Correct 0 ms 2396 KB Ok
16 Correct 0 ms 2396 KB Ok
17 Correct 0 ms 2508 KB Ok
18 Correct 1 ms 2396 KB Ok
19 Correct 0 ms 2396 KB Ok
20 Correct 1 ms 2512 KB Ok
21 Correct 1 ms 2396 KB Ok
22 Correct 0 ms 2396 KB Ok
23 Correct 1 ms 2396 KB Ok
24 Correct 3 ms 2396 KB Ok
25 Correct 3 ms 2396 KB Ok
26 Correct 3 ms 2396 KB Ok
27 Correct 2 ms 2396 KB Ok
28 Correct 2 ms 2396 KB Ok
29 Correct 2 ms 2396 KB Ok
30 Correct 2 ms 2396 KB Ok
31 Correct 2 ms 2396 KB Ok
32 Correct 4 ms 2652 KB Ok
33 Correct 2 ms 2396 KB Ok
34 Correct 5 ms 2396 KB Ok
35 Correct 5 ms 2652 KB Ok
36 Correct 5 ms 2652 KB Ok
37 Correct 5 ms 2652 KB Ok
38 Correct 5 ms 2652 KB Ok
39 Correct 5 ms 2508 KB Ok
40 Correct 5 ms 2652 KB Ok
41 Correct 5 ms 2596 KB Ok
42 Correct 8 ms 2652 KB Ok
43 Correct 5 ms 2652 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Ok
2 Correct 1 ms 2396 KB Ok
3 Correct 1 ms 2396 KB Ok
4 Correct 1 ms 2396 KB Ok
5 Correct 1 ms 2396 KB Ok
6 Correct 1 ms 2396 KB Ok
7 Correct 1 ms 2396 KB Ok
8 Correct 1 ms 2400 KB Ok
9 Correct 1 ms 2396 KB Ok
10 Correct 1 ms 2396 KB Ok
11 Correct 1 ms 2396 KB Ok
12 Correct 1 ms 2396 KB Ok
13 Correct 1 ms 2396 KB Ok
14 Correct 1 ms 2396 KB Ok
15 Correct 1 ms 2396 KB Ok
16 Correct 0 ms 2396 KB Ok
17 Correct 1 ms 2396 KB Ok
18 Correct 3 ms 2520 KB Ok
19 Correct 12 ms 2768 KB Ok
20 Correct 5 ms 2652 KB Ok
21 Correct 15 ms 2932 KB Ok
22 Correct 8 ms 2652 KB Ok
23 Correct 0 ms 2396 KB Ok
24 Correct 1 ms 2396 KB Ok
25 Correct 0 ms 2396 KB Ok
26 Correct 0 ms 2396 KB Ok
27 Correct 0 ms 2508 KB Ok
28 Correct 1 ms 2396 KB Ok
29 Correct 0 ms 2396 KB Ok
30 Correct 1 ms 2512 KB Ok
31 Correct 1 ms 2396 KB Ok
32 Correct 0 ms 2396 KB Ok
33 Correct 1 ms 2396 KB Ok
34 Correct 3 ms 2396 KB Ok
35 Correct 3 ms 2396 KB Ok
36 Correct 3 ms 2396 KB Ok
37 Correct 2 ms 2396 KB Ok
38 Correct 2 ms 2396 KB Ok
39 Correct 2 ms 2396 KB Ok
40 Correct 2 ms 2396 KB Ok
41 Correct 2 ms 2396 KB Ok
42 Correct 4 ms 2652 KB Ok
43 Correct 2 ms 2396 KB Ok
44 Correct 5 ms 2396 KB Ok
45 Correct 5 ms 2652 KB Ok
46 Correct 5 ms 2652 KB Ok
47 Correct 5 ms 2652 KB Ok
48 Correct 5 ms 2652 KB Ok
49 Correct 5 ms 2508 KB Ok
50 Correct 5 ms 2652 KB Ok
51 Correct 5 ms 2596 KB Ok
52 Correct 8 ms 2652 KB Ok
53 Correct 5 ms 2652 KB Ok
54 Correct 109 ms 6340 KB Ok
55 Correct 129 ms 8420 KB Ok
56 Correct 124 ms 8392 KB Ok
57 Correct 91 ms 5988 KB Ok
58 Correct 109 ms 8264 KB Ok
59 Correct 110 ms 8252 KB Ok
60 Correct 94 ms 7968 KB Ok
61 Correct 93 ms 7972 KB Ok
62 Correct 127 ms 8432 KB Ok
63 Correct 97 ms 6076 KB Ok
64 Correct 121 ms 6192 KB Ok
65 Correct 124 ms 8288 KB Ok
66 Correct 105 ms 6040 KB Ok
67 Correct 92 ms 6000 KB Ok
68 Correct 110 ms 8272 KB Ok
69 Correct 162 ms 12136 KB Ok
70 Correct 167 ms 13372 KB Ok
71 Correct 162 ms 11436 KB Ok
72 Correct 163 ms 12516 KB Ok
73 Correct 160 ms 11840 KB Ok
74 Correct 168 ms 10980 KB Ok
75 Correct 162 ms 10820 KB Ok
76 Correct 164 ms 13108 KB Ok
77 Correct 162 ms 10616 KB Ok
78 Correct 170 ms 12868 KB Ok
79 Correct 163 ms 12224 KB Ok
80 Correct 166 ms 11872 KB Ok
81 Correct 173 ms 12668 KB Ok
82 Correct 163 ms 12044 KB Ok
83 Correct 160 ms 11516 KB Ok

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Ok
2 Correct 1 ms 2396 KB Ok
3 Correct 1 ms 2396 KB Ok
4 Correct 1 ms 2396 KB Ok
5 Correct 1 ms 2396 KB Ok
6 Correct 1 ms 2396 KB Ok
7 Correct 1 ms 2396 KB Ok
8 Correct 1 ms 2400 KB Ok
9 Correct 1 ms 2396 KB Ok
10 Correct 1 ms 2396 KB Ok
11 Correct 1 ms 2396 KB Ok
12 Correct 1 ms 2396 KB Ok
13 Correct 1 ms 2396 KB Ok
14 Correct 1 ms 2396 KB Ok
15 Correct 1 ms 2396 KB Ok
16 Correct 0 ms 2396 KB Ok
17 Correct 1 ms 2396 KB Ok
18 Correct 3 ms 2520 KB Ok
19 Correct 12 ms 2768 KB Ok
20 Correct 5 ms 2652 KB Ok
21 Correct 15 ms 2932 KB Ok
22 Correct 8 ms 2652 KB Ok
23 Correct 0 ms 2396 KB Ok
24 Correct 1 ms 2396 KB Ok
25 Correct 0 ms 2396 KB Ok
26 Correct 0 ms 2396 KB Ok
27 Correct 0 ms 2508 KB Ok
28 Correct 1 ms 2396 KB Ok
29 Correct 0 ms 2396 KB Ok
30 Correct 1 ms 2512 KB Ok
31 Correct 1 ms 2396 KB Ok
32 Correct 0 ms 2396 KB Ok
33 Correct 1 ms 2396 KB Ok
34 Correct 1 ms 2512 KB Ok
35 Correct 1 ms 2396 KB Ok
36 Correct 1 ms 2396 KB Ok
37 Correct 1 ms 2396 KB Ok
38 Correct 1 ms 2396 KB Ok
39 Correct 127 ms 9528 KB Ok
40 Correct 114 ms 8984 KB Ok
41 Correct 231 ms 11224 KB Ok
42 Correct 158 ms 11656 KB Ok
43 Correct 96 ms 8280 KB Ok
44 Correct 162 ms 10368 KB Ok
45 Correct 3 ms 2396 KB Ok
46 Correct 3 ms 2396 KB Ok
47 Correct 3 ms 2396 KB Ok
48 Correct 2 ms 2396 KB Ok
49 Correct 2 ms 2396 KB Ok
50 Correct 2 ms 2396 KB Ok
51 Correct 2 ms 2396 KB Ok
52 Correct 2 ms 2396 KB Ok
53 Correct 4 ms 2652 KB Ok
54 Correct 2 ms 2396 KB Ok
55 Correct 5 ms 2396 KB Ok
56 Correct 5 ms 2652 KB Ok
57 Correct 5 ms 2652 KB Ok
58 Correct 5 ms 2652 KB Ok
59 Correct 5 ms 2652 KB Ok
60 Correct 5 ms 2508 KB Ok
61 Correct 5 ms 2652 KB Ok
62 Correct 5 ms 2596 KB Ok
63 Correct 8 ms 2652 KB Ok
64 Correct 5 ms 2652 KB Ok
65 Correct 109 ms 6340 KB Ok
66 Correct 129 ms 8420 KB Ok
67 Correct 124 ms 8392 KB Ok
68 Correct 91 ms 5988 KB Ok
69 Correct 109 ms 8264 KB Ok
70 Correct 110 ms 8252 KB Ok
71 Correct 94 ms 7968 KB Ok
72 Correct 93 ms 7972 KB Ok
73 Correct 127 ms 8432 KB Ok
74 Correct 97 ms 6076 KB Ok
75 Correct 121 ms 6192 KB Ok
76 Correct 124 ms 8288 KB Ok
77 Correct 105 ms 6040 KB Ok
78 Correct 92 ms 6000 KB Ok
79 Correct 110 ms 8272 KB Ok
80 Correct 162 ms 12136 KB Ok
81 Correct 167 ms 13372 KB Ok
82 Correct 162 ms 11436 KB Ok
83 Correct 163 ms 12516 KB Ok
84 Correct 160 ms 11840 KB Ok
85 Correct 168 ms 10980 KB Ok
86 Correct 162 ms 10820 KB Ok
87 Correct 164 ms 13108 KB Ok
88 Correct 162 ms 10616 KB Ok
89 Correct 170 ms 12868 KB Ok
90 Correct 163 ms 12224 KB Ok
91 Correct 166 ms 11872 KB Ok
92 Correct 173 ms 12668 KB Ok
93 Correct 163 ms 12044 KB Ok
94 Correct 160 ms 11516 KB Ok
95 Correct 267 ms 10428 KB Ok
96 Correct 411 ms 12240 KB Ok
97 Correct 392 ms 11876 KB Ok
98 Correct 303 ms 10852 KB Ok
99 Correct 362 ms 11332 KB Ok
100 Correct 363 ms 11184 KB Ok
101 Correct 375 ms 11360 KB Ok
102 Correct 342 ms 11000 KB Ok
103 Correct 359 ms 11204 KB Ok
104 Correct 415 ms 12224 KB Ok
105 Correct 375 ms 11664 KB Ok
106 Correct 329 ms 11168 KB Ok
107 Correct 390 ms 11584 KB Ok
108 Correct 415 ms 12132 KB Ok
109 Correct 365 ms 11468 KB Ok
110 Correct 714 ms 24928 KB Ok
111 Correct 740 ms 34744 KB Ok
112 Correct 712 ms 26900 KB Ok
113 Correct 731 ms 30852 KB Ok
114 Correct 737 ms 32420 KB Ok
115 Correct 750 ms 31844 KB Ok
116 Correct 730 ms 31640 KB Ok
117 Correct 730 ms 32352 KB Ok
118 Correct 708 ms 27832 KB Ok
119 Correct 737 ms 33532 KB Ok
120 Correct 716 ms 28112 KB Ok
121 Correct 726 ms 27040 KB Ok
122 Correct 706 ms 29964 KB Ok
123 Correct 719 ms 34724 KB Ok
124 Correct 703 ms 23628 KB Ok
125 Correct 730 ms 16960 KB Ok