oj.uz

Submission #54456

# Submission time Handle Problem Language Result Execution time Memory
54456 2018-07-03T13:30:11 Z egorlifar Nice sequence (IZhO18_sequence) C++17
58 / 100
 2000 ms 40404 KB 
/*
ЗАПУСКАЕМ 
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░ 
 */
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -