답안 #54457 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
54457	2018-07-03T13:31:55 Z	egorlifar	Nice sequence (IZhO18_sequence)	C++17	76 / 100	2000 ms	77188 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];


void dfs1(int u) {
    used[u] = 1;
    for (auto h: g[u]) {
        if (!used[h]) {
            dfs1(h);
        }
    }
    res[u] = timer; 
    timer++;
}



void solve(int n, int 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;
    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	23 ms	19192 KB	Ok
2	Correct	24 ms	19280 KB	Ok
3	Correct	21 ms	19308 KB	Ok
4	Correct	22 ms	19312 KB	Ok
5	Correct	21 ms	19320 KB	Ok
6	Correct	21 ms	19344 KB	Ok
7	Correct	23 ms	19344 KB	Ok
8	Correct	20 ms	19392 KB	Ok
9	Correct	22 ms	19392 KB	Ok
10	Correct	26 ms	19392 KB	Ok
11	Correct	24 ms	19392 KB	Ok
12	Correct	23 ms	19392 KB	Ok

Subtask #2
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	19392 KB	Ok
2	Correct	22 ms	19392 KB	Ok
3	Correct	23 ms	19392 KB	Ok
4	Correct	21 ms	19448 KB	Ok
5	Correct	21 ms	19448 KB	Ok
6	Correct	24 ms	19564 KB	Ok
7	Correct	38 ms	20336 KB	Ok
8	Correct	27 ms	20336 KB	Ok
9	Correct	41 ms	20620 KB	Ok
10	Correct	35 ms	20620 KB	Ok

Subtask #3
14.0 / 14.0

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

Subtask #4
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	20620 KB	Ok
2	Correct	17 ms	20620 KB	Ok
3	Correct	20 ms	20620 KB	Ok
4	Correct	16 ms	20620 KB	Ok
5	Correct	17 ms	20620 KB	Ok
6	Correct	116 ms	35388 KB	Ok
7	Correct	112 ms	35516 KB	Ok
8	Correct	236 ms	38316 KB	Ok
9	Correct	142 ms	38316 KB	Ok
10	Correct	106 ms	38316 KB	Ok
11	Correct	147 ms	39612 KB	Ok

Subtask #5
14.0 / 14.0

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

Subtask #6
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	19192 KB	Ok
2	Correct	24 ms	19280 KB	Ok
3	Correct	21 ms	19308 KB	Ok
4	Correct	22 ms	19312 KB	Ok
5	Correct	21 ms	19320 KB	Ok
6	Correct	21 ms	19344 KB	Ok
7	Correct	23 ms	19344 KB	Ok
8	Correct	20 ms	19392 KB	Ok
9	Correct	22 ms	19392 KB	Ok
10	Correct	26 ms	19392 KB	Ok
11	Correct	24 ms	19392 KB	Ok
12	Correct	23 ms	19392 KB	Ok
13	Correct	23 ms	19392 KB	Ok
14	Correct	22 ms	19392 KB	Ok
15	Correct	23 ms	19392 KB	Ok
16	Correct	21 ms	19448 KB	Ok
17	Correct	21 ms	19448 KB	Ok
18	Correct	24 ms	19564 KB	Ok
19	Correct	38 ms	20336 KB	Ok
20	Correct	27 ms	20336 KB	Ok
21	Correct	41 ms	20620 KB	Ok
22	Correct	35 ms	20620 KB	Ok
23	Correct	23 ms	20620 KB	Ok
24	Correct	21 ms	20620 KB	Ok
25	Correct	21 ms	20620 KB	Ok
26	Correct	22 ms	20620 KB	Ok
27	Correct	20 ms	20620 KB	Ok
28	Correct	21 ms	20620 KB	Ok
29	Correct	21 ms	20620 KB	Ok
30	Correct	19 ms	20620 KB	Ok
31	Correct	23 ms	20620 KB	Ok
32	Correct	22 ms	20620 KB	Ok
33	Correct	22 ms	20620 KB	Ok
34	Correct	22 ms	39612 KB	Ok
35	Correct	21 ms	39612 KB	Ok
36	Correct	22 ms	39612 KB	Ok
37	Correct	19 ms	39612 KB	Ok
38	Correct	19 ms	39612 KB	Ok
39	Correct	18 ms	39612 KB	Ok
40	Correct	19 ms	39612 KB	Ok
41	Correct	19 ms	39612 KB	Ok
42	Correct	19 ms	39612 KB	Ok
43	Correct	19 ms	39612 KB	Ok
44	Correct	21 ms	39612 KB	Ok
45	Correct	23 ms	39612 KB	Ok
46	Correct	21 ms	39612 KB	Ok
47	Correct	22 ms	39612 KB	Ok
48	Correct	22 ms	39612 KB	Ok
49	Correct	21 ms	39612 KB	Ok
50	Correct	22 ms	39612 KB	Ok
51	Correct	21 ms	39612 KB	Ok
52	Correct	23 ms	39612 KB	Ok
53	Correct	27 ms	39612 KB	Ok
54	Correct	95 ms	39612 KB	Ok
55	Correct	102 ms	39612 KB	Ok
56	Correct	176 ms	39612 KB	Ok
57	Correct	74 ms	39612 KB	Ok
58	Correct	103 ms	39612 KB	Ok
59	Correct	98 ms	39612 KB	Ok
60	Correct	96 ms	39612 KB	Ok
61	Correct	92 ms	39612 KB	Ok
62	Correct	123 ms	39612 KB	Ok
63	Correct	88 ms	39612 KB	Ok
64	Correct	120 ms	39612 KB	Ok
65	Correct	106 ms	39612 KB	Ok
66	Correct	96 ms	39612 KB	Ok
67	Correct	86 ms	39612 KB	Ok
68	Correct	111 ms	39612 KB	Ok
69	Correct	300 ms	39612 KB	Ok
70	Correct	276 ms	39612 KB	Ok
71	Correct	241 ms	39612 KB	Ok
72	Correct	367 ms	39612 KB	Ok
73	Correct	396 ms	39612 KB	Ok
74	Correct	292 ms	39612 KB	Ok
75	Correct	296 ms	39612 KB	Ok
76	Correct	343 ms	39612 KB	Ok
77	Correct	329 ms	39612 KB	Ok
78	Correct	251 ms	39612 KB	Ok
79	Correct	287 ms	39612 KB	Ok
80	Correct	285 ms	39612 KB	Ok
81	Correct	236 ms	39612 KB	Ok
82	Correct	229 ms	39612 KB	Ok
83	Correct	260 ms	39612 KB	Ok

Subtask #7
0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	19192 KB	Ok
2	Correct	24 ms	19280 KB	Ok
3	Correct	21 ms	19308 KB	Ok
4	Correct	22 ms	19312 KB	Ok
5	Correct	21 ms	19320 KB	Ok
6	Correct	21 ms	19344 KB	Ok
7	Correct	23 ms	19344 KB	Ok
8	Correct	20 ms	19392 KB	Ok
9	Correct	22 ms	19392 KB	Ok
10	Correct	26 ms	19392 KB	Ok
11	Correct	24 ms	19392 KB	Ok
12	Correct	23 ms	19392 KB	Ok
13	Correct	23 ms	19392 KB	Ok
14	Correct	22 ms	19392 KB	Ok
15	Correct	23 ms	19392 KB	Ok
16	Correct	21 ms	19448 KB	Ok
17	Correct	21 ms	19448 KB	Ok
18	Correct	24 ms	19564 KB	Ok
19	Correct	38 ms	20336 KB	Ok
20	Correct	27 ms	20336 KB	Ok
21	Correct	41 ms	20620 KB	Ok
22	Correct	35 ms	20620 KB	Ok
23	Correct	23 ms	20620 KB	Ok
24	Correct	21 ms	20620 KB	Ok
25	Correct	21 ms	20620 KB	Ok
26	Correct	22 ms	20620 KB	Ok
27	Correct	20 ms	20620 KB	Ok
28	Correct	21 ms	20620 KB	Ok
29	Correct	21 ms	20620 KB	Ok
30	Correct	19 ms	20620 KB	Ok
31	Correct	23 ms	20620 KB	Ok
32	Correct	22 ms	20620 KB	Ok
33	Correct	22 ms	20620 KB	Ok
34	Correct	17 ms	20620 KB	Ok
35	Correct	17 ms	20620 KB	Ok
36	Correct	20 ms	20620 KB	Ok
37	Correct	16 ms	20620 KB	Ok
38	Correct	17 ms	20620 KB	Ok
39	Correct	116 ms	35388 KB	Ok
40	Correct	112 ms	35516 KB	Ok
41	Correct	236 ms	38316 KB	Ok
42	Correct	142 ms	38316 KB	Ok
43	Correct	106 ms	38316 KB	Ok
44	Correct	147 ms	39612 KB	Ok
45	Correct	22 ms	39612 KB	Ok
46	Correct	21 ms	39612 KB	Ok
47	Correct	22 ms	39612 KB	Ok
48	Correct	19 ms	39612 KB	Ok
49	Correct	19 ms	39612 KB	Ok
50	Correct	18 ms	39612 KB	Ok
51	Correct	19 ms	39612 KB	Ok
52	Correct	19 ms	39612 KB	Ok
53	Correct	19 ms	39612 KB	Ok
54	Correct	19 ms	39612 KB	Ok
55	Correct	21 ms	39612 KB	Ok
56	Correct	23 ms	39612 KB	Ok
57	Correct	21 ms	39612 KB	Ok
58	Correct	22 ms	39612 KB	Ok
59	Correct	22 ms	39612 KB	Ok
60	Correct	21 ms	39612 KB	Ok
61	Correct	22 ms	39612 KB	Ok
62	Correct	21 ms	39612 KB	Ok
63	Correct	23 ms	39612 KB	Ok
64	Correct	27 ms	39612 KB	Ok
65	Correct	95 ms	39612 KB	Ok
66	Correct	102 ms	39612 KB	Ok
67	Correct	176 ms	39612 KB	Ok
68	Correct	74 ms	39612 KB	Ok
69	Correct	103 ms	39612 KB	Ok
70	Correct	98 ms	39612 KB	Ok
71	Correct	96 ms	39612 KB	Ok
72	Correct	92 ms	39612 KB	Ok
73	Correct	123 ms	39612 KB	Ok
74	Correct	88 ms	39612 KB	Ok
75	Correct	120 ms	39612 KB	Ok
76	Correct	106 ms	39612 KB	Ok
77	Correct	96 ms	39612 KB	Ok
78	Correct	86 ms	39612 KB	Ok
79	Correct	111 ms	39612 KB	Ok
80	Correct	300 ms	39612 KB	Ok
81	Correct	276 ms	39612 KB	Ok
82	Correct	241 ms	39612 KB	Ok
83	Correct	367 ms	39612 KB	Ok
84	Correct	396 ms	39612 KB	Ok
85	Correct	292 ms	39612 KB	Ok
86	Correct	296 ms	39612 KB	Ok
87	Correct	343 ms	39612 KB	Ok
88	Correct	329 ms	39612 KB	Ok
89	Correct	251 ms	39612 KB	Ok
90	Correct	287 ms	39612 KB	Ok
91	Correct	285 ms	39612 KB	Ok
92	Correct	236 ms	39612 KB	Ok
93	Correct	229 ms	39612 KB	Ok
94	Correct	260 ms	39612 KB	Ok
95	Correct	221 ms	39612 KB	Ok
96	Correct	351 ms	44220 KB	Ok
97	Correct	319 ms	44220 KB	Ok
98	Correct	227 ms	44220 KB	Ok
99	Correct	269 ms	44220 KB	Ok
100	Correct	327 ms	44220 KB	Ok
101	Correct	279 ms	44220 KB	Ok
102	Correct	309 ms	44220 KB	Ok
103	Correct	363 ms	44220 KB	Ok
104	Correct	365 ms	44220 KB	Ok
105	Correct	395 ms	44220 KB	Ok
106	Correct	385 ms	44220 KB	Ok
107	Correct	357 ms	44220 KB	Ok
108	Correct	479 ms	44340 KB	Ok
109	Correct	336 ms	44340 KB	Ok
110	Correct	1760 ms	76276 KB	Ok
111	Correct	1894 ms	77188 KB	Ok
112	Execution timed out	2013 ms	77188 KB	Time limit exceeded
113	Halted	0 ms	0 KB	-

답안 #54457

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 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
0 / 24.0