답안 #54458 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
54458	2018-07-03T13:34:15 Z	egorlifar	Nice sequence (IZhO18_sequence)	C++17	100 / 100	830 ms	64572 KB

sequence

/*
ЗАПУСКАЕМ 
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░ 
 */
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <iomanip>
#include <deque>
    
     
using namespace std;
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; } 
template<typename T, typename U> inline ostream &operator<< (ostream &_out, const pair<T, U> &_p) { _out << _p.first << ' ' << _p.second; return _out; }
template<typename T, typename U> inline istream &operator>> (istream &_in, pair<T, U> &_p) { _in >> _p.first >> _p.second; return _in; }
template<typename T> inline ostream &operator<< (ostream &_out, const vector<T> &_v) { if (_v.empty()) { return _out; } _out << _v.front(); for (auto _it = ++_v.begin(); _it != _v.end(); ++_it) { _out << ' ' << *_it; } return _out; }
template<typename T> inline istream &operator>> (istream &_in, vector<T> &_v) { for (auto &_i : _v) { _in >> _i; } return _in; }
template<typename T> inline ostream &operator<< (ostream &_out, const set<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; }
template<typename T> inline ostream &operator<< (ostream &_out, const multiset<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; }
template<typename T> inline ostream &operator<< (ostream &_out, const unordered_set<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; }
template<typename T> inline ostream &operator<< (ostream &_out, const unordered_multiset<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; }
template<typename T, typename U> inline ostream &operator<< (ostream &_out, const map<T, U> &_m) { if (_m.empty()) { return _out; } _out << '(' << _m.begin()->first << ": " << _m.begin()->second << ')'; for (auto _it = ++_m.begin(); _it != _m.end(); ++_it) { _out << ", (" << _it->first << ": " << _it->second << ')'; } return _out; }
template<typename T, typename U> inline ostream &operator<< (ostream &_out, const unordered_map<T, U> &_m) { if (_m.empty()) { return _out; } _out << '(' << _m.begin()->first << ": " << _m.begin()->second << ')'; for (auto _it = ++_m.begin(); _it != _m.end(); ++_it) { _out << ", (" << _it->first << ": " << _it->second << ')'; } return _out; }
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left228
#define right right228
#define next next228
#define rank rank228
#define prev prev228
#define y1 y1228                                                         
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define files(FILENAME) read(FILENAME), write(FILENAME)
#define pb push_back
#define x first
#define y second
const string FILENAME = "input";
const int MAXN = 400001;


vector<int> g[MAXN];
int used[MAXN];
bool bad = false;
vector<int> rg[MAXN];
long long pref[MAXN];


void dfs(int u) {
    used[u] = 1;
    for (auto h: g[u]) {
        if (!used[h]) {
            dfs(h);
            if (bad) {
                return;
            }
        } else if (used[h] == 1) {
            bad = true;
            return;
        }
    }
    used[u] = 2;
}


bool good(int len, int n, int m) {
    for (int i = 0; i <= len; i++) {
        g[i].clear();
        used[i] = false;
    }
    bad = false;
    for (int i = 1; i <= len; i++) {
        if (i >= n) {
            g[i].pb(i - n);
        } 
        if (i >= m) {
            g[i - m].pb(i);
        }
    }
    for (int i = 0; i <= len; i++) {
        if (!used[i]) {
            dfs(i);
            if (bad) {
                return false;
            }
        }
    }
    return !bad;
}


int timer = 0;
int in[MAXN];
int res[MAXN];
int nn, mm;
int lens;


void dfs1(int u) {
    used[u] = 1;
    if (u >= nn && !used[u - nn]) {
        dfs1(u - nn);
    }
    if (u + mm <= lens && !used[u + mm]) {
        dfs1(u + mm);
    }
    res[u] = timer; 
    timer++;
}



void solve(int n, int m) {
    nn = n;
    mm = m;
    if (n == m) {
        cout << n - 1 << '\n';
        for (int i = 0; i < n - 1; i++) {
            cout << 1 << ' ';
        }
        cout << '\n';
        return;
    }
    int l = 1;
    // int r = n + m;
    // while (l != r) {
    //     int mid = (l + r + 1) >> 1;
    //     if (good(mid, n, m)) {
    //         l = mid;
    //     } else {
    //         r = mid - 1;
    //     }
    // }
    l = n + m - __gcd(n, m) - 1;
    lens = l;
    for (int i = 0; i <= l; i++) {
        g[i].clear();
        rg[i].clear();
        used[i] = false;
        pref[i] = 0;
    }
    // for (int i = 1; i <= l; i++) {
    //     if (i >= n) {
    //         g[i].pb(i - n);
    //         //i < i - n
    //     } 
    // }
    // for (int i = 1; i <= l; i++) {
    //     if (i >= m) {
    //         g[i - m].pb(i);
    //     }
    // }
    timer = 0;
    for (int i = 0; i <= l; i++) {
        if (!used[i]) {
            dfs1(i);
        }
    }
    cout << l << '\n';
    for (int i = 0; i < l; i++) {
        cout << res[i] - res[i + 1] << ' ';
    }
    cout << '\n';
}
//-1 + x >= 2
//x >= 3



int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//read(FILENAME);
    int t;
    cin >> t;
    for (int it = 0; it < t; it++) {
        int n, m;
        cin >> n >> m;
        solve(n, m);
    }
}

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	19192 KB	Ok
2	Correct	17 ms	19192 KB	Ok
3	Correct	18 ms	19192 KB	Ok
4	Correct	19 ms	19244 KB	Ok
5	Correct	21 ms	19244 KB	Ok
6	Correct	20 ms	19244 KB	Ok
7	Correct	18 ms	19244 KB	Ok
8	Correct	19 ms	19244 KB	Ok
9	Correct	20 ms	19292 KB	Ok
10	Correct	18 ms	19332 KB	Ok
11	Correct	17 ms	19332 KB	Ok
12	Correct	20 ms	19384 KB	Ok

Subtask #2
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	19384 KB	Ok
2	Correct	20 ms	19384 KB	Ok
3	Correct	18 ms	19412 KB	Ok
4	Correct	19 ms	19436 KB	Ok
5	Correct	18 ms	19436 KB	Ok
6	Correct	19 ms	19456 KB	Ok
7	Correct	27 ms	20108 KB	Ok
8	Correct	21 ms	20108 KB	Ok
9	Correct	27 ms	20296 KB	Ok
10	Correct	25 ms	20296 KB	Ok

Subtask #3
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	20296 KB	Ok
2	Correct	18 ms	20296 KB	Ok
3	Correct	17 ms	20296 KB	Ok
4	Correct	17 ms	20296 KB	Ok
5	Correct	18 ms	20296 KB	Ok
6	Correct	18 ms	20296 KB	Ok
7	Correct	19 ms	20296 KB	Ok
8	Correct	18 ms	20296 KB	Ok
9	Correct	19 ms	20296 KB	Ok
10	Correct	17 ms	20296 KB	Ok
11	Correct	17 ms	20296 KB	Ok

Subtask #4
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	20296 KB	Ok
2	Correct	20 ms	20296 KB	Ok
3	Correct	17 ms	20296 KB	Ok
4	Correct	19 ms	20296 KB	Ok
5	Correct	18 ms	20296 KB	Ok
6	Correct	97 ms	30156 KB	Ok
7	Correct	84 ms	30156 KB	Ok
8	Correct	163 ms	32172 KB	Ok
9	Correct	131 ms	32172 KB	Ok
10	Correct	83 ms	32172 KB	Ok
11	Correct	119 ms	33468 KB	Ok

Subtask #5
14.0 / 14.0

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

Subtask #6
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	19192 KB	Ok
2	Correct	17 ms	19192 KB	Ok
3	Correct	18 ms	19192 KB	Ok
4	Correct	19 ms	19244 KB	Ok
5	Correct	21 ms	19244 KB	Ok
6	Correct	20 ms	19244 KB	Ok
7	Correct	18 ms	19244 KB	Ok
8	Correct	19 ms	19244 KB	Ok
9	Correct	20 ms	19292 KB	Ok
10	Correct	18 ms	19332 KB	Ok
11	Correct	17 ms	19332 KB	Ok
12	Correct	20 ms	19384 KB	Ok
13	Correct	19 ms	19384 KB	Ok
14	Correct	20 ms	19384 KB	Ok
15	Correct	18 ms	19412 KB	Ok
16	Correct	19 ms	19436 KB	Ok
17	Correct	18 ms	19436 KB	Ok
18	Correct	19 ms	19456 KB	Ok
19	Correct	27 ms	20108 KB	Ok
20	Correct	21 ms	20108 KB	Ok
21	Correct	27 ms	20296 KB	Ok
22	Correct	25 ms	20296 KB	Ok
23	Correct	18 ms	20296 KB	Ok
24	Correct	18 ms	20296 KB	Ok
25	Correct	17 ms	20296 KB	Ok
26	Correct	17 ms	20296 KB	Ok
27	Correct	18 ms	20296 KB	Ok
28	Correct	18 ms	20296 KB	Ok
29	Correct	19 ms	20296 KB	Ok
30	Correct	18 ms	20296 KB	Ok
31	Correct	19 ms	20296 KB	Ok
32	Correct	17 ms	20296 KB	Ok
33	Correct	17 ms	20296 KB	Ok
34	Correct	20 ms	33468 KB	Ok
35	Correct	19 ms	33468 KB	Ok
36	Correct	19 ms	33468 KB	Ok
37	Correct	21 ms	33468 KB	Ok
38	Correct	20 ms	33468 KB	Ok
39	Correct	19 ms	33468 KB	Ok
40	Correct	21 ms	33468 KB	Ok
41	Correct	21 ms	33468 KB	Ok
42	Correct	19 ms	33468 KB	Ok
43	Correct	18 ms	33468 KB	Ok
44	Correct	21 ms	33468 KB	Ok
45	Correct	23 ms	33468 KB	Ok
46	Correct	21 ms	33468 KB	Ok
47	Correct	20 ms	33468 KB	Ok
48	Correct	25 ms	33468 KB	Ok
49	Correct	26 ms	33468 KB	Ok
50	Correct	24 ms	33468 KB	Ok
51	Correct	23 ms	33468 KB	Ok
52	Correct	26 ms	33468 KB	Ok
53	Correct	23 ms	33468 KB	Ok
54	Correct	121 ms	33468 KB	Ok
55	Correct	101 ms	33468 KB	Ok
56	Correct	82 ms	33468 KB	Ok
57	Correct	65 ms	33468 KB	Ok
58	Correct	137 ms	33468 KB	Ok
59	Correct	105 ms	33468 KB	Ok
60	Correct	66 ms	33468 KB	Ok
61	Correct	109 ms	33468 KB	Ok
62	Correct	91 ms	33468 KB	Ok
63	Correct	73 ms	33468 KB	Ok
64	Correct	94 ms	33468 KB	Ok
65	Correct	117 ms	33468 KB	Ok
66	Correct	109 ms	33468 KB	Ok
67	Correct	71 ms	33468 KB	Ok
68	Correct	115 ms	33468 KB	Ok
69	Correct	176 ms	33468 KB	Ok
70	Correct	171 ms	33468 KB	Ok
71	Correct	159 ms	33468 KB	Ok
72	Correct	143 ms	33468 KB	Ok
73	Correct	145 ms	33468 KB	Ok
74	Correct	155 ms	33468 KB	Ok
75	Correct	155 ms	33468 KB	Ok
76	Correct	155 ms	33468 KB	Ok
77	Correct	187 ms	33468 KB	Ok
78	Correct	227 ms	33468 KB	Ok
79	Correct	167 ms	33468 KB	Ok
80	Correct	181 ms	33468 KB	Ok
81	Correct	157 ms	33468 KB	Ok
82	Correct	140 ms	33468 KB	Ok
83	Correct	151 ms	33468 KB	Ok

Subtask #7
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	19192 KB	Ok
2	Correct	17 ms	19192 KB	Ok
3	Correct	18 ms	19192 KB	Ok
4	Correct	19 ms	19244 KB	Ok
5	Correct	21 ms	19244 KB	Ok
6	Correct	20 ms	19244 KB	Ok
7	Correct	18 ms	19244 KB	Ok
8	Correct	19 ms	19244 KB	Ok
9	Correct	20 ms	19292 KB	Ok
10	Correct	18 ms	19332 KB	Ok
11	Correct	17 ms	19332 KB	Ok
12	Correct	20 ms	19384 KB	Ok
13	Correct	19 ms	19384 KB	Ok
14	Correct	20 ms	19384 KB	Ok
15	Correct	18 ms	19412 KB	Ok
16	Correct	19 ms	19436 KB	Ok
17	Correct	18 ms	19436 KB	Ok
18	Correct	19 ms	19456 KB	Ok
19	Correct	27 ms	20108 KB	Ok
20	Correct	21 ms	20108 KB	Ok
21	Correct	27 ms	20296 KB	Ok
22	Correct	25 ms	20296 KB	Ok
23	Correct	18 ms	20296 KB	Ok
24	Correct	18 ms	20296 KB	Ok
25	Correct	17 ms	20296 KB	Ok
26	Correct	17 ms	20296 KB	Ok
27	Correct	18 ms	20296 KB	Ok
28	Correct	18 ms	20296 KB	Ok
29	Correct	19 ms	20296 KB	Ok
30	Correct	18 ms	20296 KB	Ok
31	Correct	19 ms	20296 KB	Ok
32	Correct	17 ms	20296 KB	Ok
33	Correct	17 ms	20296 KB	Ok
34	Correct	19 ms	20296 KB	Ok
35	Correct	20 ms	20296 KB	Ok
36	Correct	17 ms	20296 KB	Ok
37	Correct	19 ms	20296 KB	Ok
38	Correct	18 ms	20296 KB	Ok
39	Correct	97 ms	30156 KB	Ok
40	Correct	84 ms	30156 KB	Ok
41	Correct	163 ms	32172 KB	Ok
42	Correct	131 ms	32172 KB	Ok
43	Correct	83 ms	32172 KB	Ok
44	Correct	119 ms	33468 KB	Ok
45	Correct	20 ms	33468 KB	Ok
46	Correct	19 ms	33468 KB	Ok
47	Correct	19 ms	33468 KB	Ok
48	Correct	21 ms	33468 KB	Ok
49	Correct	20 ms	33468 KB	Ok
50	Correct	19 ms	33468 KB	Ok
51	Correct	21 ms	33468 KB	Ok
52	Correct	21 ms	33468 KB	Ok
53	Correct	19 ms	33468 KB	Ok
54	Correct	18 ms	33468 KB	Ok
55	Correct	21 ms	33468 KB	Ok
56	Correct	23 ms	33468 KB	Ok
57	Correct	21 ms	33468 KB	Ok
58	Correct	20 ms	33468 KB	Ok
59	Correct	25 ms	33468 KB	Ok
60	Correct	26 ms	33468 KB	Ok
61	Correct	24 ms	33468 KB	Ok
62	Correct	23 ms	33468 KB	Ok
63	Correct	26 ms	33468 KB	Ok
64	Correct	23 ms	33468 KB	Ok
65	Correct	121 ms	33468 KB	Ok
66	Correct	101 ms	33468 KB	Ok
67	Correct	82 ms	33468 KB	Ok
68	Correct	65 ms	33468 KB	Ok
69	Correct	137 ms	33468 KB	Ok
70	Correct	105 ms	33468 KB	Ok
71	Correct	66 ms	33468 KB	Ok
72	Correct	109 ms	33468 KB	Ok
73	Correct	91 ms	33468 KB	Ok
74	Correct	73 ms	33468 KB	Ok
75	Correct	94 ms	33468 KB	Ok
76	Correct	117 ms	33468 KB	Ok
77	Correct	109 ms	33468 KB	Ok
78	Correct	71 ms	33468 KB	Ok
79	Correct	115 ms	33468 KB	Ok
80	Correct	176 ms	33468 KB	Ok
81	Correct	171 ms	33468 KB	Ok
82	Correct	159 ms	33468 KB	Ok
83	Correct	143 ms	33468 KB	Ok
84	Correct	145 ms	33468 KB	Ok
85	Correct	155 ms	33468 KB	Ok
86	Correct	155 ms	33468 KB	Ok
87	Correct	155 ms	33468 KB	Ok
88	Correct	187 ms	33468 KB	Ok
89	Correct	227 ms	33468 KB	Ok
90	Correct	167 ms	33468 KB	Ok
91	Correct	181 ms	33468 KB	Ok
92	Correct	157 ms	33468 KB	Ok
93	Correct	140 ms	33468 KB	Ok
94	Correct	151 ms	33468 KB	Ok
95	Correct	178 ms	33468 KB	Ok
96	Correct	247 ms	33468 KB	Ok
97	Correct	243 ms	33468 KB	Ok
98	Correct	214 ms	33468 KB	Ok
99	Correct	203 ms	33468 KB	Ok
100	Correct	252 ms	33468 KB	Ok
101	Correct	224 ms	33468 KB	Ok
102	Correct	245 ms	33468 KB	Ok
103	Correct	198 ms	33468 KB	Ok
104	Correct	253 ms	33468 KB	Ok
105	Correct	234 ms	33468 KB	Ok
106	Correct	199 ms	33468 KB	Ok
107	Correct	214 ms	33468 KB	Ok
108	Correct	243 ms	33480 KB	Ok
109	Correct	212 ms	33480 KB	Ok
110	Correct	566 ms	63420 KB	Ok
111	Correct	627 ms	64572 KB	Ok
112	Correct	586 ms	64572 KB	Ok
113	Correct	672 ms	64572 KB	Ok
114	Correct	671 ms	64572 KB	Ok
115	Correct	811 ms	64572 KB	Ok
116	Correct	792 ms	64572 KB	Ok
117	Correct	830 ms	64572 KB	Ok
118	Correct	675 ms	64572 KB	Ok
119	Correct	689 ms	64572 KB	Ok
120	Correct	687 ms	64572 KB	Ok
121	Correct	632 ms	64572 KB	Ok
122	Correct	634 ms	64572 KB	Ok
123	Correct	683 ms	64572 KB	Ok
124	Correct	630 ms	64572 KB	Ok
125	Correct	398 ms	64572 KB	Ok

답안 #54458

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