oj.uz

Submission #343756

# Submission time Handle Problem Language Result Execution time Memory
343756 2021-01-04T13:01:24 Z Rakhmand Nice sequence (IZhO18_sequence) C++14
76 / 100
 845 ms 61020 KB 
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <iterator>
 
using namespace std;
 
#define ios ios_base::sync_with_stdio(0), cout.tie(0), cin.tie(0);
#define S second
#define F first
#define pb push_back
#define nl '\n'
#define NL cout << '\n';
#define EX exit(0)
#define all(s) s.begin(), s.end()
#define no_answer {cout << "NO"; exit(0);}
#define FOR(i, start, finish, k) for(llong i = start; i <= finish; i += k)
 
const long long mxn = 3e5 + 110;
const long long mnn = 1e3 + 2;
const long long mod = 1e9 + 7;
const long long inf = 1e18;
const long long OO = 1e9;
 
typedef long long llong;
typedef unsigned long long ullong;
 
int n, m;
llong pr[mxn], a[mxn];
int used[mxn];
vector<int> g[mxn], top;
 
bool dfs(int x){
    used[x] = 1;
    bool ok = true;
    for(auto to : g[x]){
        if(used[to] == 0) ok = (ok & dfs(to));
        else if(used[to] == 1){
            ok = false;
        }else{
            continue;
        }
    }
    used[x] = 2;
    return ok;
    
}
 
bool check(int k){
    for(int i = 1; i <= k; i++){
        used[i] = 0;
        g[i].clear();
    }
    for(int i = 1; i + min(n, m) <= k; i++){
        if(i + n <= k)
            g[i].push_back(i + n);
        if(i + m <= k)
            g[i + m].push_back(i);
    }
    return dfs(1);
}
 
void dfss(int x){
    used[x] = 1;
    for(auto to : g[x]){
        if(used[to] == 0){
            dfss(to);
        }
    }
    top.push_back(x);
}
 
void solve(){
    cin >> n >> m;
    if(n == m){
        cout << n - 1 << nl;
        for(int i = 1; i < n; i++){
            cout << 1 << ' ';
        }
        cout << nl;
        return ;
    }
    if(n == 1 || m % n == 0){
        cout << m - 1 << nl;
        for(int i = 1; i <= m - 1; i++) cout << -1 << ' ';
        cout << nl;
        return ;
    }
    if(m == 1 || n % m == 0){
        cout << n - 1 << nl;
        for(int i = 1; i <= n - 1; i++) cout << 1 << ' ';
        cout << nl;
        return ;
    }
    int l = 0, r = n + m + 1;
    while(r - l > 1){
        int m = (l + r) / 2;
        if(check(m)){
            l = m;
        }else{
            r = m;
        }
    }
    int ans = -1;
    if(check(r)) ans = r;
    else ans = l;
    for(int i = 1; i <= ans; i++){
        used[i] = 0;
    }
    top.clear();
    cout << ans - 1 << nl;
    for(int i = 1; i <= ans; i++){
        if(used[i] == 0){
            dfss(i);
        }
    }
    reverse(top.begin(), top.end());
    for(int i = 0; i < top.size(); i++){
        pr[top[i]] = OO - i;
    }
    for(int i = 2; i <= ans; i++){
        pr[i] -= pr[1];
    }
    pr[1] = 0;
    for(int i = 2; i <= ans; i++){
        a[i] = pr[i] - pr[i - 1];
    }
    for(int i = 2; i <= ans; i++){
        cout << a[i] << ' ';
    }
    cout << nl;
}
 
int main() {
    ios;
    int t;
    cin >> t;
    while(t--){
        solve();
    }
}

Compilation message

sequence.cpp: In function 'void solve()':
sequence.cpp:136:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |     for(int i = 0; i < top.size(); i++){
      |                    ~~^~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7404 KB Ok
2 Correct 5 ms 7404 KB Ok
3 Correct 5 ms 7404 KB Ok
4 Correct 6 ms 7404 KB Ok
5 Correct 5 ms 7404 KB Ok
6 Correct 5 ms 7404 KB Ok
7 Correct 5 ms 7404 KB Ok
8 Correct 5 ms 7404 KB Ok
9 Correct 6 ms 7532 KB Ok
10 Correct 5 ms 7404 KB Ok
11 Correct 5 ms 7404 KB Ok
12 Correct 6 ms 7404 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7404 KB Ok
2 Correct 5 ms 7404 KB Ok
3 Correct 5 ms 7404 KB Ok
4 Correct 5 ms 7404 KB Ok
5 Correct 5 ms 7404 KB Ok
6 Correct 8 ms 7660 KB Ok
7 Correct 22 ms 8812 KB Ok
8 Correct 14 ms 8044 KB Ok
9 Correct 25 ms 8984 KB Ok
10 Correct 16 ms 8300 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7404 KB Ok
2 Correct 5 ms 7404 KB Ok
3 Correct 5 ms 7404 KB Ok
4 Correct 5 ms 7532 KB Ok
5 Correct 5 ms 7404 KB Ok
6 Correct 5 ms 7404 KB Ok
7 Correct 6 ms 7404 KB Ok
8 Correct 6 ms 7404 KB Ok
9 Correct 5 ms 7404 KB Ok
10 Correct 5 ms 7404 KB Ok
11 Correct 5 ms 7404 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7424 KB Ok
2 Correct 5 ms 7404 KB Ok
3 Correct 5 ms 7404 KB Ok
4 Correct 5 ms 7404 KB Ok
5 Correct 5 ms 7404 KB Ok
6 Correct 318 ms 29536 KB Ok
7 Correct 355 ms 32736 KB Ok
8 Correct 689 ms 35424 KB Ok
9 Correct 413 ms 31712 KB Ok
10 Correct 193 ms 21348 KB Ok
11 Correct 344 ms 34016 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7404 KB Ok
2 Correct 5 ms 7404 KB Ok
3 Correct 5 ms 7404 KB Ok
4 Correct 6 ms 7404 KB Ok
5 Correct 5 ms 7404 KB Ok
6 Correct 5 ms 7404 KB Ok
7 Correct 5 ms 7404 KB Ok
8 Correct 5 ms 7404 KB Ok
9 Correct 6 ms 7532 KB Ok
10 Correct 5 ms 7404 KB Ok
11 Correct 5 ms 7404 KB Ok
12 Correct 6 ms 7404 KB Ok
13 Correct 6 ms 7404 KB Ok
14 Correct 5 ms 7404 KB Ok
15 Correct 5 ms 7404 KB Ok
16 Correct 5 ms 7532 KB Ok
17 Correct 5 ms 7404 KB Ok
18 Correct 5 ms 7404 KB Ok
19 Correct 6 ms 7404 KB Ok
20 Correct 6 ms 7404 KB Ok
21 Correct 5 ms 7404 KB Ok
22 Correct 5 ms 7404 KB Ok
23 Correct 5 ms 7404 KB Ok
24 Correct 8 ms 7660 KB Ok
25 Correct 8 ms 7660 KB Ok
26 Correct 8 ms 7660 KB Ok
27 Correct 8 ms 7660 KB Ok
28 Correct 9 ms 7532 KB Ok
29 Correct 7 ms 7532 KB Ok
30 Correct 7 ms 7532 KB Ok
31 Correct 8 ms 7660 KB Ok
32 Correct 8 ms 7660 KB Ok
33 Correct 8 ms 7660 KB Ok
34 Correct 13 ms 7916 KB Ok
35 Correct 14 ms 8044 KB Ok
36 Correct 13 ms 8044 KB Ok
37 Correct 14 ms 8044 KB Ok
38 Correct 15 ms 8044 KB Ok
39 Correct 13 ms 7916 KB Ok
40 Correct 14 ms 8044 KB Ok
41 Correct 14 ms 8044 KB Ok
42 Correct 13 ms 8044 KB Ok
43 Correct 14 ms 8044 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7404 KB Ok
2 Correct 5 ms 7404 KB Ok
3 Correct 5 ms 7404 KB Ok
4 Correct 6 ms 7404 KB Ok
5 Correct 5 ms 7404 KB Ok
6 Correct 5 ms 7404 KB Ok
7 Correct 5 ms 7404 KB Ok
8 Correct 5 ms 7404 KB Ok
9 Correct 6 ms 7532 KB Ok
10 Correct 5 ms 7404 KB Ok
11 Correct 5 ms 7404 KB Ok
12 Correct 6 ms 7404 KB Ok
13 Correct 5 ms 7404 KB Ok
14 Correct 5 ms 7404 KB Ok
15 Correct 5 ms 7404 KB Ok
16 Correct 5 ms 7404 KB Ok
17 Correct 5 ms 7404 KB Ok
18 Correct 8 ms 7660 KB Ok
19 Correct 22 ms 8812 KB Ok
20 Correct 14 ms 8044 KB Ok
21 Correct 25 ms 8984 KB Ok
22 Correct 16 ms 8300 KB Ok
23 Correct 6 ms 7404 KB Ok
24 Correct 5 ms 7404 KB Ok
25 Correct 5 ms 7404 KB Ok
26 Correct 5 ms 7532 KB Ok
27 Correct 5 ms 7404 KB Ok
28 Correct 5 ms 7404 KB Ok
29 Correct 6 ms 7404 KB Ok
30 Correct 6 ms 7404 KB Ok
31 Correct 5 ms 7404 KB Ok
32 Correct 5 ms 7404 KB Ok
33 Correct 5 ms 7404 KB Ok
34 Correct 8 ms 7660 KB Ok
35 Correct 8 ms 7660 KB Ok
36 Correct 8 ms 7660 KB Ok
37 Correct 8 ms 7660 KB Ok
38 Correct 9 ms 7532 KB Ok
39 Correct 7 ms 7532 KB Ok
40 Correct 7 ms 7532 KB Ok
41 Correct 8 ms 7660 KB Ok
42 Correct 8 ms 7660 KB Ok
43 Correct 8 ms 7660 KB Ok
44 Correct 13 ms 7916 KB Ok
45 Correct 14 ms 8044 KB Ok
46 Correct 13 ms 8044 KB Ok
47 Correct 14 ms 8044 KB Ok
48 Correct 15 ms 8044 KB Ok
49 Correct 13 ms 7916 KB Ok
50 Correct 14 ms 8044 KB Ok
51 Correct 14 ms 8044 KB Ok
52 Correct 13 ms 8044 KB Ok
53 Correct 14 ms 8044 KB Ok
54 Correct 149 ms 14180 KB Ok
55 Correct 186 ms 14440 KB Ok
56 Correct 166 ms 14564 KB Ok
57 Correct 115 ms 13420 KB Ok
58 Correct 150 ms 13928 KB Ok
59 Correct 139 ms 13692 KB Ok
60 Correct 117 ms 13028 KB Ok
61 Correct 123 ms 13796 KB Ok
62 Correct 183 ms 14512 KB Ok
63 Correct 128 ms 13420 KB Ok
64 Correct 171 ms 14440 KB Ok
65 Correct 158 ms 14180 KB Ok
66 Correct 139 ms 13800 KB Ok
67 Correct 118 ms 13768 KB Ok
68 Correct 145 ms 13924 KB Ok
69 Correct 607 ms 25432 KB Ok
70 Correct 843 ms 25856 KB Ok
71 Correct 548 ms 25316 KB Ok
72 Correct 608 ms 25188 KB Ok
73 Correct 767 ms 25444 KB Ok
74 Correct 536 ms 25156 KB Ok
75 Correct 486 ms 24804 KB Ok
76 Correct 799 ms 25628 KB Ok
77 Correct 488 ms 24676 KB Ok
78 Correct 774 ms 25444 KB Ok
79 Correct 845 ms 25444 KB Ok
80 Correct 593 ms 25664 KB Ok
81 Correct 650 ms 25484 KB Ok
82 Correct 564 ms 25448 KB Ok
83 Correct 490 ms 24932 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7404 KB Ok
2 Correct 5 ms 7404 KB Ok
3 Correct 5 ms 7404 KB Ok
4 Correct 6 ms 7404 KB Ok
5 Correct 5 ms 7404 KB Ok
6 Correct 5 ms 7404 KB Ok
7 Correct 5 ms 7404 KB Ok
8 Correct 5 ms 7404 KB Ok
9 Correct 6 ms 7532 KB Ok
10 Correct 5 ms 7404 KB Ok
11 Correct 5 ms 7404 KB Ok
12 Correct 6 ms 7404 KB Ok
13 Correct 5 ms 7404 KB Ok
14 Correct 5 ms 7404 KB Ok
15 Correct 5 ms 7404 KB Ok
16 Correct 5 ms 7404 KB Ok
17 Correct 5 ms 7404 KB Ok
18 Correct 8 ms 7660 KB Ok
19 Correct 22 ms 8812 KB Ok
20 Correct 14 ms 8044 KB Ok
21 Correct 25 ms 8984 KB Ok
22 Correct 16 ms 8300 KB Ok
23 Correct 6 ms 7404 KB Ok
24 Correct 5 ms 7404 KB Ok
25 Correct 5 ms 7404 KB Ok
26 Correct 5 ms 7532 KB Ok
27 Correct 5 ms 7404 KB Ok
28 Correct 5 ms 7404 KB Ok
29 Correct 6 ms 7404 KB Ok
30 Correct 6 ms 7404 KB Ok
31 Correct 5 ms 7404 KB Ok
32 Correct 5 ms 7404 KB Ok
33 Correct 5 ms 7404 KB Ok
34 Correct 5 ms 7424 KB Ok
35 Correct 5 ms 7404 KB Ok
36 Correct 5 ms 7404 KB Ok
37 Correct 5 ms 7404 KB Ok
38 Correct 5 ms 7404 KB Ok
39 Correct 318 ms 29536 KB Ok
40 Correct 355 ms 32736 KB Ok
41 Correct 689 ms 35424 KB Ok
42 Correct 413 ms 31712 KB Ok
43 Correct 193 ms 21348 KB Ok
44 Correct 344 ms 34016 KB Ok
45 Correct 8 ms 7660 KB Ok
46 Correct 8 ms 7660 KB Ok
47 Correct 8 ms 7660 KB Ok
48 Correct 8 ms 7660 KB Ok
49 Correct 9 ms 7532 KB Ok
50 Correct 7 ms 7532 KB Ok
51 Correct 7 ms 7532 KB Ok
52 Correct 8 ms 7660 KB Ok
53 Correct 8 ms 7660 KB Ok
54 Correct 8 ms 7660 KB Ok
55 Correct 13 ms 7916 KB Ok
56 Correct 14 ms 8044 KB Ok
57 Correct 13 ms 8044 KB Ok
58 Correct 14 ms 8044 KB Ok
59 Correct 15 ms 8044 KB Ok
60 Correct 13 ms 7916 KB Ok
61 Correct 14 ms 8044 KB Ok
62 Correct 14 ms 8044 KB Ok
63 Correct 13 ms 8044 KB Ok
64 Correct 14 ms 8044 KB Ok
65 Correct 149 ms 14180 KB Ok
66 Correct 186 ms 14440 KB Ok
67 Correct 166 ms 14564 KB Ok
68 Correct 115 ms 13420 KB Ok
69 Correct 150 ms 13928 KB Ok
70 Correct 139 ms 13692 KB Ok
71 Correct 117 ms 13028 KB Ok
72 Correct 123 ms 13796 KB Ok
73 Correct 183 ms 14512 KB Ok
74 Correct 128 ms 13420 KB Ok
75 Correct 171 ms 14440 KB Ok
76 Correct 158 ms 14180 KB Ok
77 Correct 139 ms 13800 KB Ok
78 Correct 118 ms 13768 KB Ok
79 Correct 145 ms 13924 KB Ok
80 Correct 607 ms 25432 KB Ok
81 Correct 843 ms 25856 KB Ok
82 Correct 548 ms 25316 KB Ok
83 Correct 608 ms 25188 KB Ok
84 Correct 767 ms 25444 KB Ok
85 Correct 536 ms 25156 KB Ok
86 Correct 486 ms 24804 KB Ok
87 Correct 799 ms 25628 KB Ok
88 Correct 488 ms 24676 KB Ok
89 Correct 774 ms 25444 KB Ok
90 Correct 845 ms 25444 KB Ok
91 Correct 593 ms 25664 KB Ok
92 Correct 650 ms 25484 KB Ok
93 Correct 564 ms 25448 KB Ok
94 Correct 490 ms 24932 KB Ok
95 Correct 321 ms 25180 KB Ok
96 Runtime error 213 ms 61020 KB Execution killed with signal 11 (could be triggered by violating memory limits)
97 Halted 0 ms 0 KB -