답안 #54454 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
54454	2018-07-03T13:27:43 Z	egorlifar	Nice sequence (IZhO18_sequence)	C++17	76 / 100	2000 ms	42940 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);
        } else if (used[h] == 1) {
            bad = true;
        }
    }
    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);
            //i < i - n
        } 
        if (i >= m) {
            g[i - m].pb(i);
        }
    }
    for (int i = 0; i <= len; i++) {
        if (!used[i]) {
            dfs(i);
        }
    }
    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 = max(n, m) * 2;
    while (l != r) {
        int mid = (l + r + 1) >> 1;
        if (good(mid, n, m)) {
            l = mid;
        } else {
            r = mid - 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	17 ms	19064 KB	Ok
2	Correct	20 ms	19172 KB	Ok
3	Correct	17 ms	19248 KB	Ok
4	Correct	18 ms	19324 KB	Ok
5	Correct	17 ms	19356 KB	Ok
6	Correct	17 ms	19360 KB	Ok
7	Correct	19 ms	19440 KB	Ok
8	Correct	17 ms	19440 KB	Ok
9	Correct	17 ms	19440 KB	Ok
10	Correct	17 ms	19440 KB	Ok
11	Correct	18 ms	19440 KB	Ok
12	Correct	17 ms	19440 KB	Ok

Subtask #2
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	19440 KB	Ok
2	Correct	18 ms	19456 KB	Ok
3	Correct	19 ms	19488 KB	Ok
4	Correct	18 ms	19524 KB	Ok
5	Correct	18 ms	19528 KB	Ok
6	Correct	27 ms	19660 KB	Ok
7	Correct	51 ms	20560 KB	Ok
8	Correct	32 ms	20560 KB	Ok
9	Correct	56 ms	20804 KB	Ok
10	Correct	39 ms	20804 KB	Ok

Subtask #3
14.0 / 14.0

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

Subtask #4
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	20804 KB	Ok
2	Correct	17 ms	20804 KB	Ok
3	Correct	20 ms	20804 KB	Ok
4	Correct	18 ms	20804 KB	Ok
5	Correct	24 ms	20804 KB	Ok
6	Correct	569 ms	35764 KB	Ok
7	Correct	371 ms	37184 KB	Ok
8	Correct	757 ms	39540 KB	Ok
9	Correct	576 ms	39540 KB	Ok
10	Correct	347 ms	39540 KB	Ok
11	Correct	587 ms	39824 KB	Ok

Subtask #5
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	19064 KB	Ok
2	Correct	20 ms	19172 KB	Ok
3	Correct	17 ms	19248 KB	Ok
4	Correct	18 ms	19324 KB	Ok
5	Correct	17 ms	19356 KB	Ok
6	Correct	17 ms	19360 KB	Ok
7	Correct	19 ms	19440 KB	Ok
8	Correct	17 ms	19440 KB	Ok
9	Correct	17 ms	19440 KB	Ok
10	Correct	17 ms	19440 KB	Ok
11	Correct	18 ms	19440 KB	Ok
12	Correct	17 ms	19440 KB	Ok
13	Correct	19 ms	20804 KB	Ok
14	Correct	18 ms	20804 KB	Ok
15	Correct	18 ms	20804 KB	Ok
16	Correct	18 ms	20804 KB	Ok
17	Correct	18 ms	20804 KB	Ok
18	Correct	18 ms	20804 KB	Ok
19	Correct	20 ms	20804 KB	Ok
20	Correct	21 ms	20804 KB	Ok
21	Correct	21 ms	20804 KB	Ok
22	Correct	18 ms	20804 KB	Ok
23	Correct	18 ms	20804 KB	Ok
24	Correct	23 ms	39824 KB	Ok
25	Correct	23 ms	39824 KB	Ok
26	Correct	23 ms	39824 KB	Ok
27	Correct	23 ms	39824 KB	Ok
28	Correct	21 ms	39824 KB	Ok
29	Correct	21 ms	39824 KB	Ok
30	Correct	22 ms	39824 KB	Ok
31	Correct	23 ms	39824 KB	Ok
32	Correct	24 ms	39824 KB	Ok
33	Correct	23 ms	39824 KB	Ok
34	Correct	33 ms	39824 KB	Ok
35	Correct	32 ms	39824 KB	Ok
36	Correct	33 ms	39824 KB	Ok
37	Correct	33 ms	39824 KB	Ok
38	Correct	33 ms	39824 KB	Ok
39	Correct	32 ms	39824 KB	Ok
40	Correct	38 ms	39824 KB	Ok
41	Correct	45 ms	39824 KB	Ok
42	Correct	39 ms	39824 KB	Ok
43	Correct	36 ms	39824 KB	Ok

Subtask #6
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	19064 KB	Ok
2	Correct	20 ms	19172 KB	Ok
3	Correct	17 ms	19248 KB	Ok
4	Correct	18 ms	19324 KB	Ok
5	Correct	17 ms	19356 KB	Ok
6	Correct	17 ms	19360 KB	Ok
7	Correct	19 ms	19440 KB	Ok
8	Correct	17 ms	19440 KB	Ok
9	Correct	17 ms	19440 KB	Ok
10	Correct	17 ms	19440 KB	Ok
11	Correct	18 ms	19440 KB	Ok
12	Correct	17 ms	19440 KB	Ok
13	Correct	18 ms	19440 KB	Ok
14	Correct	18 ms	19456 KB	Ok
15	Correct	19 ms	19488 KB	Ok
16	Correct	18 ms	19524 KB	Ok
17	Correct	18 ms	19528 KB	Ok
18	Correct	27 ms	19660 KB	Ok
19	Correct	51 ms	20560 KB	Ok
20	Correct	32 ms	20560 KB	Ok
21	Correct	56 ms	20804 KB	Ok
22	Correct	39 ms	20804 KB	Ok
23	Correct	19 ms	20804 KB	Ok
24	Correct	18 ms	20804 KB	Ok
25	Correct	18 ms	20804 KB	Ok
26	Correct	18 ms	20804 KB	Ok
27	Correct	18 ms	20804 KB	Ok
28	Correct	18 ms	20804 KB	Ok
29	Correct	20 ms	20804 KB	Ok
30	Correct	21 ms	20804 KB	Ok
31	Correct	21 ms	20804 KB	Ok
32	Correct	18 ms	20804 KB	Ok
33	Correct	18 ms	20804 KB	Ok
34	Correct	23 ms	39824 KB	Ok
35	Correct	23 ms	39824 KB	Ok
36	Correct	23 ms	39824 KB	Ok
37	Correct	23 ms	39824 KB	Ok
38	Correct	21 ms	39824 KB	Ok
39	Correct	21 ms	39824 KB	Ok
40	Correct	22 ms	39824 KB	Ok
41	Correct	23 ms	39824 KB	Ok
42	Correct	24 ms	39824 KB	Ok
43	Correct	23 ms	39824 KB	Ok
44	Correct	33 ms	39824 KB	Ok
45	Correct	32 ms	39824 KB	Ok
46	Correct	33 ms	39824 KB	Ok
47	Correct	33 ms	39824 KB	Ok
48	Correct	33 ms	39824 KB	Ok
49	Correct	32 ms	39824 KB	Ok
50	Correct	38 ms	39824 KB	Ok
51	Correct	45 ms	39824 KB	Ok
52	Correct	39 ms	39824 KB	Ok
53	Correct	36 ms	39824 KB	Ok
54	Correct	324 ms	39824 KB	Ok
55	Correct	442 ms	39824 KB	Ok
56	Correct	408 ms	39824 KB	Ok
57	Correct	311 ms	39824 KB	Ok
58	Correct	456 ms	39824 KB	Ok
59	Correct	376 ms	39824 KB	Ok
60	Correct	378 ms	39824 KB	Ok
61	Correct	306 ms	39824 KB	Ok
62	Correct	562 ms	39824 KB	Ok
63	Correct	359 ms	39824 KB	Ok
64	Correct	593 ms	39824 KB	Ok
65	Correct	465 ms	39824 KB	Ok
66	Correct	279 ms	39824 KB	Ok
67	Correct	240 ms	39824 KB	Ok
68	Correct	520 ms	39824 KB	Ok
69	Correct	1333 ms	39824 KB	Ok
70	Correct	1566 ms	39824 KB	Ok
71	Correct	1265 ms	39824 KB	Ok
72	Correct	1333 ms	39824 KB	Ok
73	Correct	1603 ms	39824 KB	Ok
74	Correct	1607 ms	39824 KB	Ok
75	Correct	1163 ms	39824 KB	Ok
76	Correct	1903 ms	39824 KB	Ok
77	Correct	1676 ms	39824 KB	Ok
78	Correct	1906 ms	39824 KB	Ok
79	Correct	1365 ms	39824 KB	Ok
80	Correct	1530 ms	39824 KB	Ok
81	Correct	1179 ms	39824 KB	Ok
82	Correct	1046 ms	39824 KB	Ok
83	Correct	1282 ms	39824 KB	Ok

Subtask #7
0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	19064 KB	Ok
2	Correct	20 ms	19172 KB	Ok
3	Correct	17 ms	19248 KB	Ok
4	Correct	18 ms	19324 KB	Ok
5	Correct	17 ms	19356 KB	Ok
6	Correct	17 ms	19360 KB	Ok
7	Correct	19 ms	19440 KB	Ok
8	Correct	17 ms	19440 KB	Ok
9	Correct	17 ms	19440 KB	Ok
10	Correct	17 ms	19440 KB	Ok
11	Correct	18 ms	19440 KB	Ok
12	Correct	17 ms	19440 KB	Ok
13	Correct	18 ms	19440 KB	Ok
14	Correct	18 ms	19456 KB	Ok
15	Correct	19 ms	19488 KB	Ok
16	Correct	18 ms	19524 KB	Ok
17	Correct	18 ms	19528 KB	Ok
18	Correct	27 ms	19660 KB	Ok
19	Correct	51 ms	20560 KB	Ok
20	Correct	32 ms	20560 KB	Ok
21	Correct	56 ms	20804 KB	Ok
22	Correct	39 ms	20804 KB	Ok
23	Correct	19 ms	20804 KB	Ok
24	Correct	18 ms	20804 KB	Ok
25	Correct	18 ms	20804 KB	Ok
26	Correct	18 ms	20804 KB	Ok
27	Correct	18 ms	20804 KB	Ok
28	Correct	18 ms	20804 KB	Ok
29	Correct	20 ms	20804 KB	Ok
30	Correct	21 ms	20804 KB	Ok
31	Correct	21 ms	20804 KB	Ok
32	Correct	18 ms	20804 KB	Ok
33	Correct	18 ms	20804 KB	Ok
34	Correct	17 ms	20804 KB	Ok
35	Correct	17 ms	20804 KB	Ok
36	Correct	20 ms	20804 KB	Ok
37	Correct	18 ms	20804 KB	Ok
38	Correct	24 ms	20804 KB	Ok
39	Correct	569 ms	35764 KB	Ok
40	Correct	371 ms	37184 KB	Ok
41	Correct	757 ms	39540 KB	Ok
42	Correct	576 ms	39540 KB	Ok
43	Correct	347 ms	39540 KB	Ok
44	Correct	587 ms	39824 KB	Ok
45	Correct	23 ms	39824 KB	Ok
46	Correct	23 ms	39824 KB	Ok
47	Correct	23 ms	39824 KB	Ok
48	Correct	23 ms	39824 KB	Ok
49	Correct	21 ms	39824 KB	Ok
50	Correct	21 ms	39824 KB	Ok
51	Correct	22 ms	39824 KB	Ok
52	Correct	23 ms	39824 KB	Ok
53	Correct	24 ms	39824 KB	Ok
54	Correct	23 ms	39824 KB	Ok
55	Correct	33 ms	39824 KB	Ok
56	Correct	32 ms	39824 KB	Ok
57	Correct	33 ms	39824 KB	Ok
58	Correct	33 ms	39824 KB	Ok
59	Correct	33 ms	39824 KB	Ok
60	Correct	32 ms	39824 KB	Ok
61	Correct	38 ms	39824 KB	Ok
62	Correct	45 ms	39824 KB	Ok
63	Correct	39 ms	39824 KB	Ok
64	Correct	36 ms	39824 KB	Ok
65	Correct	324 ms	39824 KB	Ok
66	Correct	442 ms	39824 KB	Ok
67	Correct	408 ms	39824 KB	Ok
68	Correct	311 ms	39824 KB	Ok
69	Correct	456 ms	39824 KB	Ok
70	Correct	376 ms	39824 KB	Ok
71	Correct	378 ms	39824 KB	Ok
72	Correct	306 ms	39824 KB	Ok
73	Correct	562 ms	39824 KB	Ok
74	Correct	359 ms	39824 KB	Ok
75	Correct	593 ms	39824 KB	Ok
76	Correct	465 ms	39824 KB	Ok
77	Correct	279 ms	39824 KB	Ok
78	Correct	240 ms	39824 KB	Ok
79	Correct	520 ms	39824 KB	Ok
80	Correct	1333 ms	39824 KB	Ok
81	Correct	1566 ms	39824 KB	Ok
82	Correct	1265 ms	39824 KB	Ok
83	Correct	1333 ms	39824 KB	Ok
84	Correct	1603 ms	39824 KB	Ok
85	Correct	1607 ms	39824 KB	Ok
86	Correct	1163 ms	39824 KB	Ok
87	Correct	1903 ms	39824 KB	Ok
88	Correct	1676 ms	39824 KB	Ok
89	Correct	1906 ms	39824 KB	Ok
90	Correct	1365 ms	39824 KB	Ok
91	Correct	1530 ms	39824 KB	Ok
92	Correct	1179 ms	39824 KB	Ok
93	Correct	1046 ms	39824 KB	Ok
94	Correct	1282 ms	39824 KB	Ok
95	Correct	1257 ms	39824 KB	Ok
96	Execution timed out	2080 ms	42940 KB	Time limit exceeded
97	Halted	0 ms	0 KB	-

답안 #54454

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