답안 #58639 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
58639	2018-07-18T14:39:52 Z	Benq	Nice sequence (IZhO18_sequence)	C++14	100 / 100	1423 ms	40120 KB

sequence

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 400001;


template<int SZ> struct DSU {
    int par[SZ], sz[SZ], numComp = 0;
    DSU() {
        F0R(i,SZ) par[i] = i, sz[i] = 1;
    }
    
    int get(int x) { // path compression
    	if (par[x] != x) par[x] = get(par[x]);
    	return par[x];
    }
    
    bool unite(int x, int y) { // union-by-rank
    	x = get(x), y = get(y);
    	if (x == y) return 0;
    	numComp --;
    	if (sz[x] < sz[y]) swap(x,y);
    	sz[x] += sz[y], par[y] = x;
    	return 1;
    }
};

DSU<MX> D;

int T;

int N,M; 

void test(int x) {
    D.numComp ++;
    if (x > N) D.unite(x-N,x);
    if (x > M) D.unite(x-M,x);
}


vi flip(vi z) {
    F0R(i,sz(z)) z[i] *= -1;
    return z;
}
 
vi triN(int N, vi z) {
    if (sz(z) < N) return z;
    int tmp = 0; F0R(i,N) tmp += z[i];
    if (tmp > 0) z = flip(z);
    return z;
}
 
vi triM(int N, vi z) {
    if (sz(z) < N) return z;
    int tmp = 0; F0R(i,N) tmp += z[i];
    if (tmp < 0) z = flip(z);
    return z;
}


void solve() {
    cin >> N >> M; 
    // N = 8, M = 6;
    vi res;
    if (max(N,M) % min(N,M) == 0) {
        F0R(i,max(N,M)-1) res.pb(1);
    } else {
        D = DSU<400001>();
        int RES = 0;
        FOR(i,1,400001) {
            test(i);
            if (i > __gcd(N,M) && D.numComp == __gcd(N,M)) {
                RES = i-1;
                break;
            }
        }
        D = DSU<400001>();
        FOR(i,1,RES+1) test(i);
        FOR(i,1,RES+1) if (D.get(i) == D.get(RES+1-M)) res.pb(1);
        else res.pb(-1);
        pi x = {0,0}, y = {0,0};
        F0R(i,N) if (res[i] == 1) x.f ++; else x.s ++;
        F0R(i,M) if (res[i] == 1) y.f ++; else y.s ++;
        F0R(i,sz(res)) {
            if (res[i] == 1) res[i] *= x.s+y.s;
            else res[i] *= x.f+y.f;
        }
    }
    res = triN(N,res);
    res = triM(M,res);
    cout << sz(res) << "\n";
    for (int i: res) cout << i << " ";
    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> T;
    F0R(i,T) solve();
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	3448 KB	Ok
2	Correct	5 ms	3448 KB	Ok
3	Correct	5 ms	3608 KB	Ok
4	Correct	5 ms	3608 KB	Ok
5	Correct	6 ms	3684 KB	Ok
6	Correct	6 ms	3684 KB	Ok
7	Correct	5 ms	3684 KB	Ok
8	Correct	5 ms	3684 KB	Ok
9	Correct	6 ms	3684 KB	Ok
10	Correct	6 ms	3684 KB	Ok
11	Correct	5 ms	3684 KB	Ok
12	Correct	5 ms	3684 KB	Ok

Subtask #2
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	6740 KB	Ok
2	Correct	17 ms	6868 KB	Ok
3	Correct	17 ms	6868 KB	Ok
4	Correct	19 ms	6868 KB	Ok
5	Correct	23 ms	6892 KB	Ok
6	Correct	23 ms	6892 KB	Ok
7	Correct	34 ms	7340 KB	Ok
8	Correct	22 ms	7340 KB	Ok
9	Correct	31 ms	7356 KB	Ok
10	Correct	23 ms	7356 KB	Ok

Subtask #3
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	7356 KB	Ok
2	Correct	6 ms	7356 KB	Ok
3	Correct	20 ms	7356 KB	Ok
4	Correct	20 ms	7356 KB	Ok
5	Correct	22 ms	7356 KB	Ok
6	Correct	23 ms	7356 KB	Ok
7	Correct	22 ms	7356 KB	Ok
8	Correct	27 ms	7356 KB	Ok
9	Correct	27 ms	7356 KB	Ok
10	Correct	22 ms	7356 KB	Ok
11	Correct	20 ms	7356 KB	Ok

Subtask #4
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	29 ms	7356 KB	Ok
2	Correct	32 ms	7356 KB	Ok
3	Correct	27 ms	7356 KB	Ok
4	Correct	26 ms	7356 KB	Ok
5	Correct	33 ms	7356 KB	Ok
6	Correct	169 ms	11424 KB	Ok
7	Correct	156 ms	11424 KB	Ok
8	Correct	261 ms	13428 KB	Ok
9	Correct	222 ms	14344 KB	Ok
10	Correct	178 ms	14344 KB	Ok
11	Correct	225 ms	14344 KB	Ok

Subtask #5
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	3448 KB	Ok
2	Correct	5 ms	3448 KB	Ok
3	Correct	5 ms	3608 KB	Ok
4	Correct	5 ms	3608 KB	Ok
5	Correct	6 ms	3684 KB	Ok
6	Correct	6 ms	3684 KB	Ok
7	Correct	5 ms	3684 KB	Ok
8	Correct	5 ms	3684 KB	Ok
9	Correct	6 ms	3684 KB	Ok
10	Correct	6 ms	3684 KB	Ok
11	Correct	5 ms	3684 KB	Ok
12	Correct	5 ms	3684 KB	Ok
13	Correct	11 ms	7356 KB	Ok
14	Correct	6 ms	7356 KB	Ok
15	Correct	20 ms	7356 KB	Ok
16	Correct	20 ms	7356 KB	Ok
17	Correct	22 ms	7356 KB	Ok
18	Correct	23 ms	7356 KB	Ok
19	Correct	22 ms	7356 KB	Ok
20	Correct	27 ms	7356 KB	Ok
21	Correct	27 ms	7356 KB	Ok
22	Correct	22 ms	7356 KB	Ok
23	Correct	20 ms	7356 KB	Ok
24	Correct	23 ms	14344 KB	Ok
25	Correct	21 ms	14344 KB	Ok
26	Correct	18 ms	14344 KB	Ok
27	Correct	19 ms	14344 KB	Ok
28	Correct	22 ms	14344 KB	Ok
29	Correct	16 ms	14344 KB	Ok
30	Correct	19 ms	14344 KB	Ok
31	Correct	24 ms	14344 KB	Ok
32	Correct	23 ms	14344 KB	Ok
33	Correct	21 ms	14344 KB	Ok
34	Correct	40 ms	14344 KB	Ok
35	Correct	48 ms	14344 KB	Ok
36	Correct	48 ms	14344 KB	Ok
37	Correct	42 ms	14344 KB	Ok
38	Correct	41 ms	14344 KB	Ok
39	Correct	39 ms	14344 KB	Ok
40	Correct	43 ms	14344 KB	Ok
41	Correct	53 ms	14344 KB	Ok
42	Correct	36 ms	14344 KB	Ok
43	Correct	42 ms	14344 KB	Ok

Subtask #6
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	3448 KB	Ok
2	Correct	5 ms	3448 KB	Ok
3	Correct	5 ms	3608 KB	Ok
4	Correct	5 ms	3608 KB	Ok
5	Correct	6 ms	3684 KB	Ok
6	Correct	6 ms	3684 KB	Ok
7	Correct	5 ms	3684 KB	Ok
8	Correct	5 ms	3684 KB	Ok
9	Correct	6 ms	3684 KB	Ok
10	Correct	6 ms	3684 KB	Ok
11	Correct	5 ms	3684 KB	Ok
12	Correct	5 ms	3684 KB	Ok
13	Correct	17 ms	6740 KB	Ok
14	Correct	17 ms	6868 KB	Ok
15	Correct	17 ms	6868 KB	Ok
16	Correct	19 ms	6868 KB	Ok
17	Correct	23 ms	6892 KB	Ok
18	Correct	23 ms	6892 KB	Ok
19	Correct	34 ms	7340 KB	Ok
20	Correct	22 ms	7340 KB	Ok
21	Correct	31 ms	7356 KB	Ok
22	Correct	23 ms	7356 KB	Ok
23	Correct	11 ms	7356 KB	Ok
24	Correct	6 ms	7356 KB	Ok
25	Correct	20 ms	7356 KB	Ok
26	Correct	20 ms	7356 KB	Ok
27	Correct	22 ms	7356 KB	Ok
28	Correct	23 ms	7356 KB	Ok
29	Correct	22 ms	7356 KB	Ok
30	Correct	27 ms	7356 KB	Ok
31	Correct	27 ms	7356 KB	Ok
32	Correct	22 ms	7356 KB	Ok
33	Correct	20 ms	7356 KB	Ok
34	Correct	23 ms	14344 KB	Ok
35	Correct	21 ms	14344 KB	Ok
36	Correct	18 ms	14344 KB	Ok
37	Correct	19 ms	14344 KB	Ok
38	Correct	22 ms	14344 KB	Ok
39	Correct	16 ms	14344 KB	Ok
40	Correct	19 ms	14344 KB	Ok
41	Correct	24 ms	14344 KB	Ok
42	Correct	23 ms	14344 KB	Ok
43	Correct	21 ms	14344 KB	Ok
44	Correct	40 ms	14344 KB	Ok
45	Correct	48 ms	14344 KB	Ok
46	Correct	48 ms	14344 KB	Ok
47	Correct	42 ms	14344 KB	Ok
48	Correct	41 ms	14344 KB	Ok
49	Correct	39 ms	14344 KB	Ok
50	Correct	43 ms	14344 KB	Ok
51	Correct	53 ms	14344 KB	Ok
52	Correct	36 ms	14344 KB	Ok
53	Correct	42 ms	14344 KB	Ok
54	Correct	140 ms	14344 KB	Ok
55	Correct	164 ms	14344 KB	Ok
56	Correct	138 ms	14344 KB	Ok
57	Correct	114 ms	14344 KB	Ok
58	Correct	123 ms	14344 KB	Ok
59	Correct	135 ms	14344 KB	Ok
60	Correct	117 ms	14344 KB	Ok
61	Correct	123 ms	14344 KB	Ok
62	Correct	206 ms	14344 KB	Ok
63	Correct	106 ms	14344 KB	Ok
64	Correct	190 ms	14344 KB	Ok
65	Correct	186 ms	14344 KB	Ok
66	Correct	117 ms	14344 KB	Ok
67	Correct	100 ms	14344 KB	Ok
68	Correct	184 ms	14344 KB	Ok
69	Correct	294 ms	14712 KB	Ok
70	Correct	352 ms	15060 KB	Ok
71	Correct	282 ms	15060 KB	Ok
72	Correct	304 ms	15060 KB	Ok
73	Correct	292 ms	15060 KB	Ok
74	Correct	309 ms	15060 KB	Ok
75	Correct	283 ms	15060 KB	Ok
76	Correct	261 ms	15060 KB	Ok
77	Correct	271 ms	15060 KB	Ok
78	Correct	320 ms	15060 KB	Ok
79	Correct	279 ms	15112 KB	Ok
80	Correct	270 ms	15112 KB	Ok
81	Correct	242 ms	15112 KB	Ok
82	Correct	240 ms	15112 KB	Ok
83	Correct	274 ms	15112 KB	Ok

Subtask #7
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	3448 KB	Ok
2	Correct	5 ms	3448 KB	Ok
3	Correct	5 ms	3608 KB	Ok
4	Correct	5 ms	3608 KB	Ok
5	Correct	6 ms	3684 KB	Ok
6	Correct	6 ms	3684 KB	Ok
7	Correct	5 ms	3684 KB	Ok
8	Correct	5 ms	3684 KB	Ok
9	Correct	6 ms	3684 KB	Ok
10	Correct	6 ms	3684 KB	Ok
11	Correct	5 ms	3684 KB	Ok
12	Correct	5 ms	3684 KB	Ok
13	Correct	17 ms	6740 KB	Ok
14	Correct	17 ms	6868 KB	Ok
15	Correct	17 ms	6868 KB	Ok
16	Correct	19 ms	6868 KB	Ok
17	Correct	23 ms	6892 KB	Ok
18	Correct	23 ms	6892 KB	Ok
19	Correct	34 ms	7340 KB	Ok
20	Correct	22 ms	7340 KB	Ok
21	Correct	31 ms	7356 KB	Ok
22	Correct	23 ms	7356 KB	Ok
23	Correct	11 ms	7356 KB	Ok
24	Correct	6 ms	7356 KB	Ok
25	Correct	20 ms	7356 KB	Ok
26	Correct	20 ms	7356 KB	Ok
27	Correct	22 ms	7356 KB	Ok
28	Correct	23 ms	7356 KB	Ok
29	Correct	22 ms	7356 KB	Ok
30	Correct	27 ms	7356 KB	Ok
31	Correct	27 ms	7356 KB	Ok
32	Correct	22 ms	7356 KB	Ok
33	Correct	20 ms	7356 KB	Ok
34	Correct	29 ms	7356 KB	Ok
35	Correct	32 ms	7356 KB	Ok
36	Correct	27 ms	7356 KB	Ok
37	Correct	26 ms	7356 KB	Ok
38	Correct	33 ms	7356 KB	Ok
39	Correct	169 ms	11424 KB	Ok
40	Correct	156 ms	11424 KB	Ok
41	Correct	261 ms	13428 KB	Ok
42	Correct	222 ms	14344 KB	Ok
43	Correct	178 ms	14344 KB	Ok
44	Correct	225 ms	14344 KB	Ok
45	Correct	23 ms	14344 KB	Ok
46	Correct	21 ms	14344 KB	Ok
47	Correct	18 ms	14344 KB	Ok
48	Correct	19 ms	14344 KB	Ok
49	Correct	22 ms	14344 KB	Ok
50	Correct	16 ms	14344 KB	Ok
51	Correct	19 ms	14344 KB	Ok
52	Correct	24 ms	14344 KB	Ok
53	Correct	23 ms	14344 KB	Ok
54	Correct	21 ms	14344 KB	Ok
55	Correct	40 ms	14344 KB	Ok
56	Correct	48 ms	14344 KB	Ok
57	Correct	48 ms	14344 KB	Ok
58	Correct	42 ms	14344 KB	Ok
59	Correct	41 ms	14344 KB	Ok
60	Correct	39 ms	14344 KB	Ok
61	Correct	43 ms	14344 KB	Ok
62	Correct	53 ms	14344 KB	Ok
63	Correct	36 ms	14344 KB	Ok
64	Correct	42 ms	14344 KB	Ok
65	Correct	140 ms	14344 KB	Ok
66	Correct	164 ms	14344 KB	Ok
67	Correct	138 ms	14344 KB	Ok
68	Correct	114 ms	14344 KB	Ok
69	Correct	123 ms	14344 KB	Ok
70	Correct	135 ms	14344 KB	Ok
71	Correct	117 ms	14344 KB	Ok
72	Correct	123 ms	14344 KB	Ok
73	Correct	206 ms	14344 KB	Ok
74	Correct	106 ms	14344 KB	Ok
75	Correct	190 ms	14344 KB	Ok
76	Correct	186 ms	14344 KB	Ok
77	Correct	117 ms	14344 KB	Ok
78	Correct	100 ms	14344 KB	Ok
79	Correct	184 ms	14344 KB	Ok
80	Correct	294 ms	14712 KB	Ok
81	Correct	352 ms	15060 KB	Ok
82	Correct	282 ms	15060 KB	Ok
83	Correct	304 ms	15060 KB	Ok
84	Correct	292 ms	15060 KB	Ok
85	Correct	309 ms	15060 KB	Ok
86	Correct	283 ms	15060 KB	Ok
87	Correct	261 ms	15060 KB	Ok
88	Correct	271 ms	15060 KB	Ok
89	Correct	320 ms	15060 KB	Ok
90	Correct	279 ms	15112 KB	Ok
91	Correct	270 ms	15112 KB	Ok
92	Correct	242 ms	15112 KB	Ok
93	Correct	240 ms	15112 KB	Ok
94	Correct	274 ms	15112 KB	Ok
95	Correct	232 ms	15112 KB	Ok
96	Correct	403 ms	19244 KB	Ok
97	Correct	453 ms	19244 KB	Ok
98	Correct	266 ms	19244 KB	Ok
99	Correct	374 ms	19244 KB	Ok
100	Correct	450 ms	19244 KB	Ok
101	Correct	359 ms	19244 KB	Ok
102	Correct	378 ms	19244 KB	Ok
103	Correct	378 ms	19244 KB	Ok
104	Correct	364 ms	19244 KB	Ok
105	Correct	385 ms	19308 KB	Ok
106	Correct	269 ms	19308 KB	Ok
107	Correct	517 ms	19308 KB	Ok
108	Correct	539 ms	19700 KB	Ok
109	Correct	333 ms	19700 KB	Ok
110	Correct	950 ms	37656 KB	Ok
111	Correct	1162 ms	38748 KB	Ok
112	Correct	1229 ms	39120 KB	Ok
113	Correct	972 ms	39120 KB	Ok
114	Correct	1423 ms	39756 KB	Ok
115	Correct	1254 ms	39756 KB	Ok
116	Correct	1298 ms	39756 KB	Ok
117	Correct	1244 ms	39756 KB	Ok
118	Correct	1043 ms	39756 KB	Ok
119	Correct	1401 ms	39756 KB	Ok
120	Correct	1234 ms	39756 KB	Ok
121	Correct	1067 ms	39756 KB	Ok
122	Correct	1270 ms	39756 KB	Ok
123	Correct	1374 ms	39756 KB	Ok
124	Correct	1302 ms	40120 KB	Ok
125	Correct	720 ms	40120 KB	Ok

답안 #58639

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 9.0 / 9.0

Subtask #3 14.0 / 14.0

Subtask #4 15.0 / 15.0

Subtask #5 14.0 / 14.0

Subtask #6 18.0 / 18.0

Subtask #7 24.0 / 24.0

Subtask #1
6.0 / 6.0

Subtask #2
9.0 / 9.0

Subtask #3
14.0 / 14.0

Subtask #4
15.0 / 15.0

Subtask #5
14.0 / 14.0

Subtask #6
18.0 / 18.0

Subtask #7
24.0 / 24.0