답안 #54456 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
54456	2018-07-03T13:30:11 Z	egorlifar	Nice sequence (IZhO18_sequence)	C++17	58 / 100	2000 ms	40404 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();
    }
    memset(used, 0, sizeof(used));
    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;
        }
    }
    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	21 ms	20728 KB	Ok
2	Correct	24 ms	20836 KB	Ok
3	Correct	23 ms	20836 KB	Ok
4	Correct	19 ms	20864 KB	Ok
5	Correct	20 ms	20868 KB	Ok
6	Correct	18 ms	20900 KB	Ok
7	Correct	20 ms	20900 KB	Ok
8	Correct	18 ms	21028 KB	Ok
9	Correct	19 ms	21028 KB	Ok
10	Correct	19 ms	21028 KB	Ok
11	Correct	19 ms	21028 KB	Ok
12	Correct	17 ms	21028 KB	Ok

Subtask #2
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	21028 KB	Ok
2	Correct	21 ms	21028 KB	Ok
3	Correct	23 ms	21028 KB	Ok
4	Correct	22 ms	21028 KB	Ok
5	Correct	23 ms	21028 KB	Ok
6	Correct	31 ms	21092 KB	Ok
7	Correct	55 ms	21988 KB	Ok
8	Correct	39 ms	21988 KB	Ok
9	Correct	63 ms	22276 KB	Ok
10	Correct	45 ms	22276 KB	Ok

Subtask #3
14.0 / 14.0

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

Subtask #4
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	22276 KB	Ok
2	Correct	22 ms	22276 KB	Ok
3	Correct	23 ms	22276 KB	Ok
4	Correct	22 ms	22276 KB	Ok
5	Correct	23 ms	22276 KB	Ok
6	Correct	578 ms	36364 KB	Ok
7	Correct	399 ms	37816 KB	Ok
8	Correct	799 ms	40108 KB	Ok
9	Correct	577 ms	40108 KB	Ok
10	Correct	352 ms	40108 KB	Ok
11	Correct	659 ms	40404 KB	Ok

Subtask #5
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	20728 KB	Ok
2	Correct	24 ms	20836 KB	Ok
3	Correct	23 ms	20836 KB	Ok
4	Correct	19 ms	20864 KB	Ok
5	Correct	20 ms	20868 KB	Ok
6	Correct	18 ms	20900 KB	Ok
7	Correct	20 ms	20900 KB	Ok
8	Correct	18 ms	21028 KB	Ok
9	Correct	19 ms	21028 KB	Ok
10	Correct	19 ms	21028 KB	Ok
11	Correct	19 ms	21028 KB	Ok
12	Correct	17 ms	21028 KB	Ok
13	Correct	19 ms	22276 KB	Ok
14	Correct	23 ms	22276 KB	Ok
15	Correct	20 ms	22276 KB	Ok
16	Correct	20 ms	22276 KB	Ok
17	Correct	20 ms	22276 KB	Ok
18	Correct	20 ms	22276 KB	Ok
19	Correct	19 ms	22276 KB	Ok
20	Correct	20 ms	22276 KB	Ok
21	Correct	20 ms	22276 KB	Ok
22	Correct	21 ms	22276 KB	Ok
23	Correct	20 ms	22276 KB	Ok
24	Correct	31 ms	40404 KB	Ok
25	Correct	30 ms	40404 KB	Ok
26	Correct	33 ms	40404 KB	Ok
27	Correct	31 ms	40404 KB	Ok
28	Correct	36 ms	40404 KB	Ok
29	Correct	33 ms	40404 KB	Ok
30	Correct	33 ms	40404 KB	Ok
31	Correct	30 ms	40404 KB	Ok
32	Correct	31 ms	40404 KB	Ok
33	Correct	29 ms	40404 KB	Ok
34	Correct	48 ms	40404 KB	Ok
35	Correct	46 ms	40404 KB	Ok
36	Correct	47 ms	40404 KB	Ok
37	Correct	40 ms	40404 KB	Ok
38	Correct	38 ms	40404 KB	Ok
39	Correct	39 ms	40404 KB	Ok
40	Correct	42 ms	40404 KB	Ok
41	Correct	40 ms	40404 KB	Ok
42	Correct	49 ms	40404 KB	Ok
43	Correct	41 ms	40404 KB	Ok

Subtask #6
0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	20728 KB	Ok
2	Correct	24 ms	20836 KB	Ok
3	Correct	23 ms	20836 KB	Ok
4	Correct	19 ms	20864 KB	Ok
5	Correct	20 ms	20868 KB	Ok
6	Correct	18 ms	20900 KB	Ok
7	Correct	20 ms	20900 KB	Ok
8	Correct	18 ms	21028 KB	Ok
9	Correct	19 ms	21028 KB	Ok
10	Correct	19 ms	21028 KB	Ok
11	Correct	19 ms	21028 KB	Ok
12	Correct	17 ms	21028 KB	Ok
13	Correct	20 ms	21028 KB	Ok
14	Correct	21 ms	21028 KB	Ok
15	Correct	23 ms	21028 KB	Ok
16	Correct	22 ms	21028 KB	Ok
17	Correct	23 ms	21028 KB	Ok
18	Correct	31 ms	21092 KB	Ok
19	Correct	55 ms	21988 KB	Ok
20	Correct	39 ms	21988 KB	Ok
21	Correct	63 ms	22276 KB	Ok
22	Correct	45 ms	22276 KB	Ok
23	Correct	19 ms	22276 KB	Ok
24	Correct	23 ms	22276 KB	Ok
25	Correct	20 ms	22276 KB	Ok
26	Correct	20 ms	22276 KB	Ok
27	Correct	20 ms	22276 KB	Ok
28	Correct	20 ms	22276 KB	Ok
29	Correct	19 ms	22276 KB	Ok
30	Correct	20 ms	22276 KB	Ok
31	Correct	20 ms	22276 KB	Ok
32	Correct	21 ms	22276 KB	Ok
33	Correct	20 ms	22276 KB	Ok
34	Correct	31 ms	40404 KB	Ok
35	Correct	30 ms	40404 KB	Ok
36	Correct	33 ms	40404 KB	Ok
37	Correct	31 ms	40404 KB	Ok
38	Correct	36 ms	40404 KB	Ok
39	Correct	33 ms	40404 KB	Ok
40	Correct	33 ms	40404 KB	Ok
41	Correct	30 ms	40404 KB	Ok
42	Correct	31 ms	40404 KB	Ok
43	Correct	29 ms	40404 KB	Ok
44	Correct	48 ms	40404 KB	Ok
45	Correct	46 ms	40404 KB	Ok
46	Correct	47 ms	40404 KB	Ok
47	Correct	40 ms	40404 KB	Ok
48	Correct	38 ms	40404 KB	Ok
49	Correct	39 ms	40404 KB	Ok
50	Correct	42 ms	40404 KB	Ok
51	Correct	40 ms	40404 KB	Ok
52	Correct	49 ms	40404 KB	Ok
53	Correct	41 ms	40404 KB	Ok
54	Correct	270 ms	40404 KB	Ok
55	Correct	335 ms	40404 KB	Ok
56	Correct	327 ms	40404 KB	Ok
57	Correct	206 ms	40404 KB	Ok
58	Correct	381 ms	40404 KB	Ok
59	Correct	341 ms	40404 KB	Ok
60	Correct	319 ms	40404 KB	Ok
61	Correct	283 ms	40404 KB	Ok
62	Correct	496 ms	40404 KB	Ok
63	Correct	415 ms	40404 KB	Ok
64	Correct	379 ms	40404 KB	Ok
65	Correct	339 ms	40404 KB	Ok
66	Correct	290 ms	40404 KB	Ok
67	Correct	254 ms	40404 KB	Ok
68	Correct	407 ms	40404 KB	Ok
69	Correct	940 ms	40404 KB	Ok
70	Correct	1289 ms	40404 KB	Ok
71	Correct	982 ms	40404 KB	Ok
72	Correct	1150 ms	40404 KB	Ok
73	Correct	1224 ms	40404 KB	Ok
74	Correct	1592 ms	40404 KB	Ok
75	Correct	1407 ms	40404 KB	Ok
76	Correct	1370 ms	40404 KB	Ok
77	Correct	1425 ms	40404 KB	Ok
78	Execution timed out	2074 ms	40404 KB	Time limit exceeded
79	Halted	0 ms	0 KB	-

Subtask #7
0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	20728 KB	Ok
2	Correct	24 ms	20836 KB	Ok
3	Correct	23 ms	20836 KB	Ok
4	Correct	19 ms	20864 KB	Ok
5	Correct	20 ms	20868 KB	Ok
6	Correct	18 ms	20900 KB	Ok
7	Correct	20 ms	20900 KB	Ok
8	Correct	18 ms	21028 KB	Ok
9	Correct	19 ms	21028 KB	Ok
10	Correct	19 ms	21028 KB	Ok
11	Correct	19 ms	21028 KB	Ok
12	Correct	17 ms	21028 KB	Ok
13	Correct	20 ms	21028 KB	Ok
14	Correct	21 ms	21028 KB	Ok
15	Correct	23 ms	21028 KB	Ok
16	Correct	22 ms	21028 KB	Ok
17	Correct	23 ms	21028 KB	Ok
18	Correct	31 ms	21092 KB	Ok
19	Correct	55 ms	21988 KB	Ok
20	Correct	39 ms	21988 KB	Ok
21	Correct	63 ms	22276 KB	Ok
22	Correct	45 ms	22276 KB	Ok
23	Correct	19 ms	22276 KB	Ok
24	Correct	23 ms	22276 KB	Ok
25	Correct	20 ms	22276 KB	Ok
26	Correct	20 ms	22276 KB	Ok
27	Correct	20 ms	22276 KB	Ok
28	Correct	20 ms	22276 KB	Ok
29	Correct	19 ms	22276 KB	Ok
30	Correct	20 ms	22276 KB	Ok
31	Correct	20 ms	22276 KB	Ok
32	Correct	21 ms	22276 KB	Ok
33	Correct	20 ms	22276 KB	Ok
34	Correct	21 ms	22276 KB	Ok
35	Correct	22 ms	22276 KB	Ok
36	Correct	23 ms	22276 KB	Ok
37	Correct	22 ms	22276 KB	Ok
38	Correct	23 ms	22276 KB	Ok
39	Correct	578 ms	36364 KB	Ok
40	Correct	399 ms	37816 KB	Ok
41	Correct	799 ms	40108 KB	Ok
42	Correct	577 ms	40108 KB	Ok
43	Correct	352 ms	40108 KB	Ok
44	Correct	659 ms	40404 KB	Ok
45	Correct	31 ms	40404 KB	Ok
46	Correct	30 ms	40404 KB	Ok
47	Correct	33 ms	40404 KB	Ok
48	Correct	31 ms	40404 KB	Ok
49	Correct	36 ms	40404 KB	Ok
50	Correct	33 ms	40404 KB	Ok
51	Correct	33 ms	40404 KB	Ok
52	Correct	30 ms	40404 KB	Ok
53	Correct	31 ms	40404 KB	Ok
54	Correct	29 ms	40404 KB	Ok
55	Correct	48 ms	40404 KB	Ok
56	Correct	46 ms	40404 KB	Ok
57	Correct	47 ms	40404 KB	Ok
58	Correct	40 ms	40404 KB	Ok
59	Correct	38 ms	40404 KB	Ok
60	Correct	39 ms	40404 KB	Ok
61	Correct	42 ms	40404 KB	Ok
62	Correct	40 ms	40404 KB	Ok
63	Correct	49 ms	40404 KB	Ok
64	Correct	41 ms	40404 KB	Ok
65	Correct	270 ms	40404 KB	Ok
66	Correct	335 ms	40404 KB	Ok
67	Correct	327 ms	40404 KB	Ok
68	Correct	206 ms	40404 KB	Ok
69	Correct	381 ms	40404 KB	Ok
70	Correct	341 ms	40404 KB	Ok
71	Correct	319 ms	40404 KB	Ok
72	Correct	283 ms	40404 KB	Ok
73	Correct	496 ms	40404 KB	Ok
74	Correct	415 ms	40404 KB	Ok
75	Correct	379 ms	40404 KB	Ok
76	Correct	339 ms	40404 KB	Ok
77	Correct	290 ms	40404 KB	Ok
78	Correct	254 ms	40404 KB	Ok
79	Correct	407 ms	40404 KB	Ok
80	Correct	940 ms	40404 KB	Ok
81	Correct	1289 ms	40404 KB	Ok
82	Correct	982 ms	40404 KB	Ok
83	Correct	1150 ms	40404 KB	Ok
84	Correct	1224 ms	40404 KB	Ok
85	Correct	1592 ms	40404 KB	Ok
86	Correct	1407 ms	40404 KB	Ok
87	Correct	1370 ms	40404 KB	Ok
88	Correct	1425 ms	40404 KB	Ok
89	Execution timed out	2074 ms	40404 KB	Time limit exceeded
90	Halted	0 ms	0 KB	-

답안 #54456

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

Subtask #7
0 / 24.0