oj.uz

Submission #498543

# Submission time Handle Problem Language Result Execution time Memory
498543 2021-12-25T12:23:36 Z Ierus Nice sequence (IZhO18_sequence) C++17
15 / 100
 17 ms 13728 KB 
#include<bits/stdc++.h>
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
*/
using namespace std;
#pragma GCC optimize ("unroll-loops,Ofast,O3")
#pragma GCC target("avx,avx2,fma")
#define F first
#define S second
#define sz(x) (int)x.size()
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define NFS ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
//#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
typedef long long ll;
const int E = 1e6+777;
const long long inf = 1e18+777;
const int N = 5e5+777;
const int MOD = 1e9+7;
const bool I = 1;
int n, m;
bool used[N];
vector<int> ts, ans, g[N];
void dfs(int v){
	used[v] = 1;
	for(auto to : g[v]){
		if(!used[to]){
			dfs(to);
		}
	}
	ts.pb(v);
}
void check(int R){
	memset(used,0,sizeof(used));
	for(int i = 0; i <= R; ++i){
		if(i - n >= 0) g[i].pb(i-n);
		if(i + m <= R) g[i].pb(i+m);
	}
	for(int i = 0; i <= R; ++i){
		if(!used[i]) dfs(i);
	}
	reverse(all(ts));
	vector<int> pref(R+1, 0);
	ans.clear();
	int cnt = 0;
//	cerr << "TS\n";
	for(int x : ts){
//		cerr << x << ' ';
		pref[x] = cnt++;
	}
//	cerr << '\n';
	ts.clear();
	for(int i = 1; i <= R; ++i){
		ans.pb(pref[i] - pref[i-1]);
	}
}
int main(){auto solve=[&](){
	cin >> n >> m;
	int len = n + m - 1 - __gcd(n, m);
	check(len);
	cout << sz(ans) << '\n';
	for(auto it : ans){
		cout << it << ' ';
	}cout << '\n';
	for(int i = 0; i <= n; ++i){
		g[i].clear();
	}
};NFS;int T=1;if(I)cin>>T;while(T--)solve();}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12492 KB Ok
2 Correct 6 ms 12512 KB Ok
3 Correct 6 ms 12468 KB Ok
4 Correct 7 ms 12512 KB Ok
5 Correct 7 ms 12492 KB Ok
6 Correct 6 ms 12492 KB Ok
7 Correct 7 ms 12568 KB Ok
8 Correct 7 ms 12456 KB Ok
9 Correct 8 ms 12464 KB Ok
10 Correct 9 ms 12464 KB Ok
11 Correct 7 ms 12464 KB Ok
12 Correct 7 ms 12452 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12492 KB Ok
2 Correct 6 ms 12492 KB Ok
3 Correct 6 ms 12492 KB Ok
4 Correct 6 ms 12464 KB Ok
5 Correct 6 ms 12492 KB Ok
6 Correct 8 ms 12748 KB Ok
7 Correct 15 ms 13548 KB Ok
8 Correct 13 ms 12976 KB Ok
9 Correct 17 ms 13728 KB Ok
10 Correct 13 ms 13184 KB Ok

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12492 KB Ok
2 Correct 6 ms 12500 KB Ok
3 Correct 6 ms 12456 KB Ok
4 Correct 6 ms 12492 KB Ok
5 Correct 6 ms 12464 KB Ok
6 Incorrect 7 ms 12464 KB there is incorrect sequence
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 12492 KB there is incorrect sequence
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12492 KB Ok
2 Correct 6 ms 12512 KB Ok
3 Correct 6 ms 12468 KB Ok
4 Correct 7 ms 12512 KB Ok
5 Correct 7 ms 12492 KB Ok
6 Correct 6 ms 12492 KB Ok
7 Correct 7 ms 12568 KB Ok
8 Correct 7 ms 12456 KB Ok
9 Correct 8 ms 12464 KB Ok
10 Correct 9 ms 12464 KB Ok
11 Correct 7 ms 12464 KB Ok
12 Correct 7 ms 12452 KB Ok
13 Correct 7 ms 12492 KB Ok
14 Correct 6 ms 12500 KB Ok
15 Correct 6 ms 12456 KB Ok
16 Correct 6 ms 12492 KB Ok
17 Correct 6 ms 12464 KB Ok
18 Incorrect 7 ms 12464 KB there is incorrect sequence
19 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12492 KB Ok
2 Correct 6 ms 12512 KB Ok
3 Correct 6 ms 12468 KB Ok
4 Correct 7 ms 12512 KB Ok
5 Correct 7 ms 12492 KB Ok
6 Correct 6 ms 12492 KB Ok
7 Correct 7 ms 12568 KB Ok
8 Correct 7 ms 12456 KB Ok
9 Correct 8 ms 12464 KB Ok
10 Correct 9 ms 12464 KB Ok
11 Correct 7 ms 12464 KB Ok
12 Correct 7 ms 12452 KB Ok
13 Correct 6 ms 12492 KB Ok
14 Correct 6 ms 12492 KB Ok
15 Correct 6 ms 12492 KB Ok
16 Correct 6 ms 12464 KB Ok
17 Correct 6 ms 12492 KB Ok
18 Correct 8 ms 12748 KB Ok
19 Correct 15 ms 13548 KB Ok
20 Correct 13 ms 12976 KB Ok
21 Correct 17 ms 13728 KB Ok
22 Correct 13 ms 13184 KB Ok
23 Correct 7 ms 12492 KB Ok
24 Correct 6 ms 12500 KB Ok
25 Correct 6 ms 12456 KB Ok
26 Correct 6 ms 12492 KB Ok
27 Correct 6 ms 12464 KB Ok
28 Incorrect 7 ms 12464 KB there is incorrect sequence
29 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12492 KB Ok
2 Correct 6 ms 12512 KB Ok
3 Correct 6 ms 12468 KB Ok
4 Correct 7 ms 12512 KB Ok
5 Correct 7 ms 12492 KB Ok
6 Correct 6 ms 12492 KB Ok
7 Correct 7 ms 12568 KB Ok
8 Correct 7 ms 12456 KB Ok
9 Correct 8 ms 12464 KB Ok
10 Correct 9 ms 12464 KB Ok
11 Correct 7 ms 12464 KB Ok
12 Correct 7 ms 12452 KB Ok
13 Correct 6 ms 12492 KB Ok
14 Correct 6 ms 12492 KB Ok
15 Correct 6 ms 12492 KB Ok
16 Correct 6 ms 12464 KB Ok
17 Correct 6 ms 12492 KB Ok
18 Correct 8 ms 12748 KB Ok
19 Correct 15 ms 13548 KB Ok
20 Correct 13 ms 12976 KB Ok
21 Correct 17 ms 13728 KB Ok
22 Correct 13 ms 13184 KB Ok
23 Correct 7 ms 12492 KB Ok
24 Correct 6 ms 12500 KB Ok
25 Correct 6 ms 12456 KB Ok
26 Correct 6 ms 12492 KB Ok
27 Correct 6 ms 12464 KB Ok
28 Incorrect 7 ms 12464 KB there is incorrect sequence
29 Halted 0 ms 0 KB -