oj.uz

Submission #1116737

# Submission time Handle Problem Language Result Execution time Memory
1116737 2024-11-22T09:12:35 Z vjudge1 Nice sequence (IZhO18_sequence) C++17
15 / 100
 507 ms 840 KB 
#include <bits/stdc++.h>
#pragma optimize("g", on)
#pragma GCC optimize ("inline")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("03")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,avx2,mmx,fma,avx,tune=native")
void Freopen () {
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
}
using namespace std;
#define fi first
#define se second
// #define int long long
const int N = 2e6 + 7, M = 2e5 + 7;
int pref[N];
void solve() {
	int n, m;
	cin>>n>>m;
	int sz = n + m - __gcd(n, m) - 1; 
	// if(min(n, m) == 2) {
	// 	if(n == 2) {
	// 		if(m % 2 == 0) {
	// 			cout << m - 1 << '\n';
	// 			for(int i = 1; i < m; i++)cout << -1 << ' ';
	// 			cout << '\n';
	// 		}else {
	// 			cout << m << '\n';
	// 			int x = m + 1, y = -(m + 2);
	// 			for(int i = 1; i <= m; i++) {
	// 				if(i % 2)cout << x << ' ';
	// 				else cout << y << ' '; 
	// 			}
	// 			cout << '\n';
	// 		}
	// 	}else {
	// 		if(n % 2 == 0) {
	// 			cout << n - 1 << '\n';
	// 			for(int i = 1; i < n; i++)cout << 1 << ' ';
	// 			cout << '\n';
	// 		}else {
	// 			cout << n << '\n';
	// 			int x = n + 2, y = -(n + 1);
	// 			for(int i = 1; i <= n; i++) {
	// 				if(i % 2)cout << y << ' ';
	// 				else cout << x << ' '; 
	// 			}
	// 			cout << '\n';
	// 		}
	// 	}
	// 	return;
	// }
	// if(__gcd(max(n, m), min(n, m)) == min(n, m)) {
	// 	if(n < m) {
	// 		cout << m - 1 << '\n';
	// 		for(int i = 1; i < m; i++)cout << -1 << ' ';
	// 		cout << '\n';
	// 	}else {
	// 		cout << n - 1 << '\n';
	// 		for(int i = 1; i < n; i++)cout << 1 << ' ';
	// 		cout << '\n';
	// 	}
	// 	return;
	// }
	if(n < m) {
		int mxx = 0;
		vector<int> vec;
		for(int jj = 1; jj <= M; jj++) { 
			int x = jj, y = -(jj * (n - 1) + 1);
			int pos = sz;
			for(int i = 1; i <= sz; i++) {
				int j = (i % n == 0 ? y : x);
				pref[i] = pref[i - 1] + j;
				if(i >= n && (pref[i] - pref[i - n]) >= 0) {
					pos = i - 1;
					break;
				}
				if(i >= m && (pref[i] - pref[i - m]) <= 0) {
					pos = i - 1;
					break;
				}
			}
			if(mxx < pos) {
				mxx = pos;
				vec.clear();
				for(int i = 1; i <= pos; i++) {
					vec.push_back((i % n == 0 ? y : x));
				}
				if(mxx == sz)break;
			}
		}
		cout << mxx << '\n';
		for(auto j : vec)cout << j << ' ';
		cout << '\n';
	}else {
		int mxx = 0;
		vector<int> vec;
		for(int jj = 1; jj <= M; jj++) {
			int x = -jj, y = jj * (m - 1) + 1;
			int pos = sz;
			for(int i = 1; i <= sz; i++) {
				int j = (i % m == 0 ? y : x);
				pref[i] = pref[i - 1] + j;
				if(i >= n && (pref[i] - pref[i - n]) >= 0) {
					pos = i - 1;
					break;
				}
				if(i >= m && (pref[i] - pref[i - m]) <= 0) {
					pos = i - 1;
					break;
				}
			}
			if(mxx < pos) {
				mxx = pos;
				vec.clear();
				for(int i = 1; i <= pos; i++) {
					vec.push_back((i % m == 0 ? y : x));
				}
				if(mxx == sz)break;
			}
		}
		cout << mxx << '\n';
		for(auto j : vec)cout << j << ' ';
		cout << '\n';
	}
}
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//Freopen();
	int T = 1;
	cin>>T;
	while(T --)solve();
}
/*

*/

Compilation message

sequence.cpp:2: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    2 | #pragma optimize("g", on)
      | 
sequence.cpp: In function 'void Freopen()':
sequence.cpp:10:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:11:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     freopen("output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Ok
2 Correct 1 ms 336 KB Ok
3 Correct 1 ms 504 KB Ok
4 Correct 1 ms 336 KB Ok
5 Correct 1 ms 336 KB Ok
6 Correct 17 ms 528 KB Ok
7 Correct 367 ms 832 KB Ok
8 Correct 83 ms 584 KB Ok
9 Correct 507 ms 840 KB Ok
10 Correct 166 ms 584 KB Ok

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Ok
2 Correct 1 ms 336 KB Ok
3 Correct 1 ms 336 KB Ok
4 Incorrect 7 ms 336 KB Jury has the better answer : jans = 9, pans = 8
5 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 336 KB Jury has the better answer : jans = 6, pans = 5
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Ok
2 Correct 1 ms 336 KB Ok
3 Correct 1 ms 336 KB Ok
4 Correct 1 ms 336 KB Ok
5 Correct 1 ms 336 KB Ok
6 Correct 1 ms 336 KB Ok
7 Correct 1 ms 336 KB Ok
8 Correct 1 ms 336 KB Ok
9 Correct 1 ms 336 KB Ok
10 Correct 1 ms 336 KB Ok
11 Correct 1 ms 384 KB Ok
12 Correct 1 ms 336 KB Ok
13 Correct 1 ms 504 KB Ok
14 Correct 1 ms 336 KB Ok
15 Correct 1 ms 336 KB Ok
16 Incorrect 7 ms 336 KB Jury has the better answer : jans = 9, pans = 8
17 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Ok
2 Correct 1 ms 336 KB Ok
3 Correct 1 ms 336 KB Ok
4 Correct 1 ms 336 KB Ok
5 Correct 1 ms 336 KB Ok
6 Correct 1 ms 336 KB Ok
7 Correct 1 ms 336 KB Ok
8 Correct 1 ms 336 KB Ok
9 Correct 1 ms 336 KB Ok
10 Correct 1 ms 336 KB Ok
11 Correct 1 ms 384 KB Ok
12 Correct 1 ms 336 KB Ok
13 Correct 1 ms 336 KB Ok
14 Correct 1 ms 336 KB Ok
15 Correct 1 ms 504 KB Ok
16 Correct 1 ms 336 KB Ok
17 Correct 1 ms 336 KB Ok
18 Correct 17 ms 528 KB Ok
19 Correct 367 ms 832 KB Ok
20 Correct 83 ms 584 KB Ok
21 Correct 507 ms 840 KB Ok
22 Correct 166 ms 584 KB Ok
23 Correct 1 ms 504 KB Ok
24 Correct 1 ms 336 KB Ok
25 Correct 1 ms 336 KB Ok
26 Incorrect 7 ms 336 KB Jury has the better answer : jans = 9, pans = 8
27 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Ok
2 Correct 1 ms 336 KB Ok
3 Correct 1 ms 336 KB Ok
4 Correct 1 ms 336 KB Ok
5 Correct 1 ms 336 KB Ok
6 Correct 1 ms 336 KB Ok
7 Correct 1 ms 336 KB Ok
8 Correct 1 ms 336 KB Ok
9 Correct 1 ms 336 KB Ok
10 Correct 1 ms 336 KB Ok
11 Correct 1 ms 384 KB Ok
12 Correct 1 ms 336 KB Ok
13 Correct 1 ms 336 KB Ok
14 Correct 1 ms 336 KB Ok
15 Correct 1 ms 504 KB Ok
16 Correct 1 ms 336 KB Ok
17 Correct 1 ms 336 KB Ok
18 Correct 17 ms 528 KB Ok
19 Correct 367 ms 832 KB Ok
20 Correct 83 ms 584 KB Ok
21 Correct 507 ms 840 KB Ok
22 Correct 166 ms 584 KB Ok
23 Correct 1 ms 504 KB Ok
24 Correct 1 ms 336 KB Ok
25 Correct 1 ms 336 KB Ok
26 Incorrect 7 ms 336 KB Jury has the better answer : jans = 9, pans = 8
27 Halted 0 ms 0 KB -