oj.uz

Submission #1116739

# Submission time Handle Problem Language Result Execution time Memory
1116739 2024-11-22T09:16:01 Z vjudge1 Nice sequence (IZhO18_sequence) C++17
15 / 100
 505 ms 844 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) + __gcd(n, m));
			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) + __gcd(n, m);
			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 504 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 504 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 336 KB Ok
4 Correct 1 ms 336 KB Ok
5 Correct 1 ms 504 KB Ok
6 Correct 16 ms 336 KB Ok
7 Correct 366 ms 844 KB Ok
8 Correct 83 ms 588 KB Ok
9 Correct 505 ms 840 KB Ok
10 Correct 165 ms 592 KB Ok

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Ok
2 Correct 1 ms 336 KB Ok
3 Correct 1 ms 336 KB Ok
4 Incorrect 10 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 10 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 504 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 504 KB Ok
12 Correct 1 ms 336 KB Ok
13 Correct 1 ms 348 KB Ok
14 Correct 1 ms 336 KB Ok
15 Correct 1 ms 336 KB Ok
16 Incorrect 10 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 504 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 504 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 336 KB Ok
16 Correct 1 ms 336 KB Ok
17 Correct 1 ms 504 KB Ok
18 Correct 16 ms 336 KB Ok
19 Correct 366 ms 844 KB Ok
20 Correct 83 ms 588 KB Ok
21 Correct 505 ms 840 KB Ok
22 Correct 165 ms 592 KB Ok
23 Correct 1 ms 348 KB Ok
24 Correct 1 ms 336 KB Ok
25 Correct 1 ms 336 KB Ok
26 Incorrect 10 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 504 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 504 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 336 KB Ok
16 Correct 1 ms 336 KB Ok
17 Correct 1 ms 504 KB Ok
18 Correct 16 ms 336 KB Ok
19 Correct 366 ms 844 KB Ok
20 Correct 83 ms 588 KB Ok
21 Correct 505 ms 840 KB Ok
22 Correct 165 ms 592 KB Ok
23 Correct 1 ms 348 KB Ok
24 Correct 1 ms 336 KB Ok
25 Correct 1 ms 336 KB Ok
26 Incorrect 10 ms 336 KB Jury has the better answer : jans = 9, pans = 8
27 Halted 0 ms 0 KB -