oj.uz

Submission #343754

# Submission time Handle Problem Language Result Execution time Memory
343754 2021-01-04T12:59:10 Z Rakhmand Nice sequence (IZhO18_sequence) C++14
76 / 100
 2000 ms 64236 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 = 4e5 + 110;
const long long mnn = 1e3 + 2;
const long long mod = 1e9 + 7;
const long long inf = 1e18;
const long long OO = 1e8;
 
typedef long long llong;
typedef unsigned long long ullong;
 
int n, m, 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() {
    int t;
    cin >> t;
    while(t--){
        solve();
    }
}

Compilation message

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

Subtask #1
6.0 / 6.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9708 KB Ok
2 Correct 7 ms 9708 KB Ok
3 Correct 7 ms 9708 KB Ok
4 Correct 7 ms 9708 KB Ok
5 Correct 8 ms 9836 KB Ok
6 Correct 11 ms 9964 KB Ok
7 Correct 27 ms 11116 KB Ok
8 Correct 16 ms 10348 KB Ok
9 Correct 35 ms 11244 KB Ok
10 Correct 20 ms 10604 KB Ok

Subtask #3
14.0 / 14.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9708 KB Ok
2 Correct 7 ms 9708 KB Ok
3 Correct 7 ms 9708 KB Ok
4 Correct 7 ms 9708 KB Ok
5 Correct 7 ms 9708 KB Ok
6 Correct 349 ms 30696 KB Ok
7 Correct 390 ms 33508 KB Ok
8 Correct 721 ms 36068 KB Ok
9 Correct 448 ms 32872 KB Ok
10 Correct 214 ms 22756 KB Ok
11 Correct 382 ms 34912 KB Ok

Subtask #5
14.0 / 14.0

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

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9708 KB Ok
2 Correct 7 ms 9708 KB Ok
3 Correct 7 ms 9708 KB Ok
4 Correct 7 ms 9708 KB Ok
5 Correct 8 ms 9708 KB Ok
6 Correct 7 ms 9708 KB Ok
7 Correct 7 ms 9708 KB Ok
8 Correct 8 ms 9708 KB Ok
9 Correct 7 ms 9708 KB Ok
10 Correct 7 ms 9708 KB Ok
11 Correct 7 ms 9708 KB Ok
12 Correct 7 ms 9708 KB Ok
13 Correct 7 ms 9708 KB Ok
14 Correct 7 ms 9708 KB Ok
15 Correct 7 ms 9708 KB Ok
16 Correct 7 ms 9708 KB Ok
17 Correct 8 ms 9836 KB Ok
18 Correct 11 ms 9964 KB Ok
19 Correct 27 ms 11116 KB Ok
20 Correct 16 ms 10348 KB Ok
21 Correct 35 ms 11244 KB Ok
22 Correct 20 ms 10604 KB Ok
23 Correct 7 ms 9728 KB Ok
24 Correct 7 ms 9708 KB Ok
25 Correct 7 ms 9836 KB Ok
26 Correct 7 ms 9836 KB Ok
27 Correct 7 ms 9708 KB Ok
28 Correct 7 ms 9708 KB Ok
29 Correct 7 ms 9708 KB Ok
30 Correct 7 ms 9708 KB Ok
31 Correct 7 ms 9708 KB Ok
32 Correct 7 ms 9708 KB Ok
33 Correct 7 ms 9708 KB Ok
34 Correct 10 ms 9964 KB Ok
35 Correct 10 ms 9964 KB Ok
36 Correct 10 ms 9964 KB Ok
37 Correct 10 ms 9964 KB Ok
38 Correct 9 ms 9836 KB Ok
39 Correct 9 ms 9836 KB Ok
40 Correct 9 ms 9836 KB Ok
41 Correct 11 ms 9964 KB Ok
42 Correct 10 ms 9964 KB Ok
43 Correct 10 ms 9964 KB Ok
44 Correct 16 ms 10348 KB Ok
45 Correct 17 ms 10348 KB Ok
46 Correct 16 ms 10348 KB Ok
47 Correct 17 ms 10348 KB Ok
48 Correct 16 ms 10348 KB Ok
49 Correct 16 ms 10220 KB Ok
50 Correct 17 ms 10348 KB Ok
51 Correct 17 ms 10348 KB Ok
52 Correct 17 ms 10348 KB Ok
53 Correct 18 ms 10348 KB Ok
54 Correct 168 ms 15716 KB Ok
55 Correct 225 ms 16100 KB Ok
56 Correct 192 ms 16232 KB Ok
57 Correct 128 ms 15204 KB Ok
58 Correct 166 ms 15588 KB Ok
59 Correct 149 ms 15204 KB Ok
60 Correct 124 ms 14700 KB Ok
61 Correct 135 ms 15336 KB Ok
62 Correct 200 ms 15844 KB Ok
63 Correct 143 ms 15204 KB Ok
64 Correct 193 ms 16104 KB Ok
65 Correct 179 ms 15716 KB Ok
66 Correct 151 ms 15460 KB Ok
67 Correct 131 ms 15204 KB Ok
68 Correct 161 ms 15612 KB Ok
69 Correct 638 ms 26800 KB Ok
70 Correct 953 ms 27412 KB Ok
71 Correct 590 ms 26856 KB Ok
72 Correct 660 ms 26856 KB Ok
73 Correct 705 ms 26856 KB Ok
74 Correct 546 ms 26600 KB Ok
75 Correct 505 ms 26348 KB Ok
76 Correct 909 ms 27372 KB Ok
77 Correct 522 ms 26348 KB Ok
78 Correct 784 ms 26988 KB Ok
79 Correct 826 ms 27116 KB Ok
80 Correct 644 ms 27368 KB Ok
81 Correct 643 ms 26856 KB Ok
82 Correct 627 ms 26984 KB Ok
83 Correct 529 ms 26600 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9708 KB Ok
2 Correct 7 ms 9708 KB Ok
3 Correct 7 ms 9708 KB Ok
4 Correct 7 ms 9708 KB Ok
5 Correct 8 ms 9708 KB Ok
6 Correct 7 ms 9708 KB Ok
7 Correct 7 ms 9708 KB Ok
8 Correct 8 ms 9708 KB Ok
9 Correct 7 ms 9708 KB Ok
10 Correct 7 ms 9708 KB Ok
11 Correct 7 ms 9708 KB Ok
12 Correct 7 ms 9708 KB Ok
13 Correct 7 ms 9708 KB Ok
14 Correct 7 ms 9708 KB Ok
15 Correct 7 ms 9708 KB Ok
16 Correct 7 ms 9708 KB Ok
17 Correct 8 ms 9836 KB Ok
18 Correct 11 ms 9964 KB Ok
19 Correct 27 ms 11116 KB Ok
20 Correct 16 ms 10348 KB Ok
21 Correct 35 ms 11244 KB Ok
22 Correct 20 ms 10604 KB Ok
23 Correct 7 ms 9728 KB Ok
24 Correct 7 ms 9708 KB Ok
25 Correct 7 ms 9836 KB Ok
26 Correct 7 ms 9836 KB Ok
27 Correct 7 ms 9708 KB Ok
28 Correct 7 ms 9708 KB Ok
29 Correct 7 ms 9708 KB Ok
30 Correct 7 ms 9708 KB Ok
31 Correct 7 ms 9708 KB Ok
32 Correct 7 ms 9708 KB Ok
33 Correct 7 ms 9708 KB Ok
34 Correct 7 ms 9708 KB Ok
35 Correct 7 ms 9708 KB Ok
36 Correct 7 ms 9708 KB Ok
37 Correct 7 ms 9708 KB Ok
38 Correct 7 ms 9708 KB Ok
39 Correct 349 ms 30696 KB Ok
40 Correct 390 ms 33508 KB Ok
41 Correct 721 ms 36068 KB Ok
42 Correct 448 ms 32872 KB Ok
43 Correct 214 ms 22756 KB Ok
44 Correct 382 ms 34912 KB Ok
45 Correct 10 ms 9964 KB Ok
46 Correct 10 ms 9964 KB Ok
47 Correct 10 ms 9964 KB Ok
48 Correct 10 ms 9964 KB Ok
49 Correct 9 ms 9836 KB Ok
50 Correct 9 ms 9836 KB Ok
51 Correct 9 ms 9836 KB Ok
52 Correct 11 ms 9964 KB Ok
53 Correct 10 ms 9964 KB Ok
54 Correct 10 ms 9964 KB Ok
55 Correct 16 ms 10348 KB Ok
56 Correct 17 ms 10348 KB Ok
57 Correct 16 ms 10348 KB Ok
58 Correct 17 ms 10348 KB Ok
59 Correct 16 ms 10348 KB Ok
60 Correct 16 ms 10220 KB Ok
61 Correct 17 ms 10348 KB Ok
62 Correct 17 ms 10348 KB Ok
63 Correct 17 ms 10348 KB Ok
64 Correct 18 ms 10348 KB Ok
65 Correct 168 ms 15716 KB Ok
66 Correct 225 ms 16100 KB Ok
67 Correct 192 ms 16232 KB Ok
68 Correct 128 ms 15204 KB Ok
69 Correct 166 ms 15588 KB Ok
70 Correct 149 ms 15204 KB Ok
71 Correct 124 ms 14700 KB Ok
72 Correct 135 ms 15336 KB Ok
73 Correct 200 ms 15844 KB Ok
74 Correct 143 ms 15204 KB Ok
75 Correct 193 ms 16104 KB Ok
76 Correct 179 ms 15716 KB Ok
77 Correct 151 ms 15460 KB Ok
78 Correct 131 ms 15204 KB Ok
79 Correct 161 ms 15612 KB Ok
80 Correct 638 ms 26800 KB Ok
81 Correct 953 ms 27412 KB Ok
82 Correct 590 ms 26856 KB Ok
83 Correct 660 ms 26856 KB Ok
84 Correct 705 ms 26856 KB Ok
85 Correct 546 ms 26600 KB Ok
86 Correct 505 ms 26348 KB Ok
87 Correct 909 ms 27372 KB Ok
88 Correct 522 ms 26348 KB Ok
89 Correct 784 ms 26988 KB Ok
90 Correct 826 ms 27116 KB Ok
91 Correct 644 ms 27368 KB Ok
92 Correct 643 ms 26856 KB Ok
93 Correct 627 ms 26984 KB Ok
94 Correct 529 ms 26600 KB Ok
95 Correct 362 ms 25952 KB Ok
96 Correct 641 ms 32740 KB Ok
97 Correct 676 ms 28508 KB Ok
98 Correct 395 ms 28416 KB Ok
99 Correct 543 ms 28496 KB Ok
100 Correct 621 ms 27228 KB Ok
101 Correct 593 ms 30604 KB Ok
102 Correct 537 ms 28384 KB Ok
103 Correct 551 ms 29668 KB Ok
104 Correct 716 ms 31580 KB Ok
105 Correct 681 ms 31984 KB Ok
106 Correct 500 ms 32604 KB Ok
107 Correct 577 ms 31068 KB Ok
108 Correct 721 ms 31972 KB Ok
109 Correct 630 ms 33376 KB Ok
110 Execution timed out 2058 ms 64236 KB Time limit exceeded
111 Halted 0 ms 0 KB -