oj.uz

Submission #513591

# Submission time Handle Problem Language Result Execution time Memory
513591 2022-01-17T09:38:32 Z Killer2501 Nice sequence (IZhO18_sequence) C++14
76 / 100
 692 ms 58800 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 3e5+5;
const int M = (1<<17);
const ll inf = 1e15;
const ll mod = 1e15+7;
int n, t, k, m, d[N], in[N], out[N];
ll ans, tong, a[N], b[N], c[N];
string s[N];
struct node
{
    int x[2];
    set<int> vi;
    node(){}
    node( int _x, int _y)
    {
        x[0] = _x;
        x[1] = _y;
    }

};
vector<node> q;
vector<int> adj[N], kq;
void dfs(int u)
{
    a[u] = ++t;
    if(u+m <= k && a[u+m] == 0)dfs(u+m);
    if(u-n >= 0 && a[u-n] == 0)dfs(u-n);
}
bool check(int mid)
{
    k = mid;
    for(int i = 0; i <= k; i ++)adj[i].clear();
    fill_n(a, k+1, 0);
    t = 0;
    for(int i = 0; i <= k; i ++)
    {
        if(i+m <= k)
        {
            adj[i].pb(i+m);
            ++a[i+m];
        }
        if(i >= n)
        {
            adj[i].pb(i-n);
            ++a[i-n];
        }
    }
    queue<int> q;
    for(int i = 0; i <= k; i ++)if(a[i] == 0)q.push(i);
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        a[u] = ++t;
        for(int v: adj[u])
        {
            --a[v];
            if(a[v] == 0)q.push(v);
        }
    }
    if(t == k+1)return true;
    return false;
}
void sol()
{
    cin >> n >> m;
    int l = 1, r = 5e5, mid;
    while(l <= r)
    {
        mid = (l+r)>>1;
        if(check(mid))l = mid+1;
        else r = mid-1;
    }
    check(r);
    cout << r << '\n';
    for(int i = 1; i <= r; i ++)cout << a[i]-a[i-1] <<" ";
    cout << '\n';
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    #define task "test"
    if(fopen(task".inp", "r"))
	{
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
    }
    int ntest = 1;
    cin >> ntest;
    while(ntest -- > 0)
    sol();
}

Compilation message

sequence.cpp: In function 'int main()':
sequence.cpp:96:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |   freopen(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:97:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 26436 KB Ok
2 Correct 114 ms 26540 KB Ok
3 Correct 104 ms 26540 KB Ok
4 Correct 105 ms 26472 KB Ok
5 Correct 113 ms 26540 KB Ok
6 Correct 105 ms 26540 KB Ok
7 Correct 105 ms 26436 KB Ok
8 Correct 104 ms 26516 KB Ok
9 Correct 111 ms 26496 KB Ok
10 Correct 111 ms 26436 KB Ok
11 Correct 103 ms 26536 KB Ok
12 Correct 105 ms 26536 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 26536 KB Ok
2 Correct 108 ms 26536 KB Ok
3 Correct 108 ms 26536 KB Ok
4 Correct 102 ms 26492 KB Ok
5 Correct 102 ms 26480 KB Ok
6 Correct 108 ms 26572 KB Ok
7 Correct 131 ms 26992 KB Ok
8 Correct 111 ms 26684 KB Ok
9 Correct 126 ms 26824 KB Ok
10 Correct 115 ms 26664 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 26536 KB Ok
2 Correct 105 ms 26600 KB Ok
3 Correct 109 ms 26540 KB Ok
4 Correct 106 ms 26544 KB Ok
5 Correct 104 ms 26544 KB Ok
6 Correct 116 ms 26540 KB Ok
7 Correct 107 ms 26564 KB Ok
8 Correct 103 ms 26472 KB Ok
9 Correct 102 ms 26536 KB Ok
10 Correct 104 ms 26444 KB Ok
11 Correct 104 ms 26536 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 26564 KB Ok
2 Correct 102 ms 26540 KB Ok
3 Correct 108 ms 26540 KB Ok
4 Correct 109 ms 26492 KB Ok
5 Correct 113 ms 26496 KB Ok
6 Correct 340 ms 29400 KB Ok
7 Correct 304 ms 28780 KB Ok
8 Correct 542 ms 30920 KB Ok
9 Correct 412 ms 31352 KB Ok
10 Correct 278 ms 28284 KB Ok
11 Correct 440 ms 30232 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 26436 KB Ok
2 Correct 114 ms 26540 KB Ok
3 Correct 104 ms 26540 KB Ok
4 Correct 105 ms 26472 KB Ok
5 Correct 113 ms 26540 KB Ok
6 Correct 105 ms 26540 KB Ok
7 Correct 105 ms 26436 KB Ok
8 Correct 104 ms 26516 KB Ok
9 Correct 111 ms 26496 KB Ok
10 Correct 111 ms 26436 KB Ok
11 Correct 103 ms 26536 KB Ok
12 Correct 105 ms 26536 KB Ok
13 Correct 51 ms 26536 KB Ok
14 Correct 105 ms 26600 KB Ok
15 Correct 109 ms 26540 KB Ok
16 Correct 106 ms 26544 KB Ok
17 Correct 104 ms 26544 KB Ok
18 Correct 116 ms 26540 KB Ok
19 Correct 107 ms 26564 KB Ok
20 Correct 103 ms 26472 KB Ok
21 Correct 102 ms 26536 KB Ok
22 Correct 104 ms 26444 KB Ok
23 Correct 104 ms 26536 KB Ok
24 Correct 111 ms 26676 KB Ok
25 Correct 105 ms 26560 KB Ok
26 Correct 106 ms 26560 KB Ok
27 Correct 109 ms 26576 KB Ok
28 Correct 106 ms 26684 KB Ok
29 Correct 104 ms 26552 KB Ok
30 Correct 106 ms 26556 KB Ok
31 Correct 107 ms 26612 KB Ok
32 Correct 119 ms 26572 KB Ok
33 Correct 111 ms 26552 KB Ok
34 Correct 119 ms 26556 KB Ok
35 Correct 122 ms 26764 KB Ok
36 Correct 118 ms 26648 KB Ok
37 Correct 111 ms 26776 KB Ok
38 Correct 109 ms 26608 KB Ok
39 Correct 110 ms 26636 KB Ok
40 Correct 115 ms 26672 KB Ok
41 Correct 116 ms 26692 KB Ok
42 Correct 110 ms 26612 KB Ok
43 Correct 111 ms 26704 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 26436 KB Ok
2 Correct 114 ms 26540 KB Ok
3 Correct 104 ms 26540 KB Ok
4 Correct 105 ms 26472 KB Ok
5 Correct 113 ms 26540 KB Ok
6 Correct 105 ms 26540 KB Ok
7 Correct 105 ms 26436 KB Ok
8 Correct 104 ms 26516 KB Ok
9 Correct 111 ms 26496 KB Ok
10 Correct 111 ms 26436 KB Ok
11 Correct 103 ms 26536 KB Ok
12 Correct 105 ms 26536 KB Ok
13 Correct 109 ms 26536 KB Ok
14 Correct 108 ms 26536 KB Ok
15 Correct 108 ms 26536 KB Ok
16 Correct 102 ms 26492 KB Ok
17 Correct 102 ms 26480 KB Ok
18 Correct 108 ms 26572 KB Ok
19 Correct 131 ms 26992 KB Ok
20 Correct 111 ms 26684 KB Ok
21 Correct 126 ms 26824 KB Ok
22 Correct 115 ms 26664 KB Ok
23 Correct 51 ms 26536 KB Ok
24 Correct 105 ms 26600 KB Ok
25 Correct 109 ms 26540 KB Ok
26 Correct 106 ms 26544 KB Ok
27 Correct 104 ms 26544 KB Ok
28 Correct 116 ms 26540 KB Ok
29 Correct 107 ms 26564 KB Ok
30 Correct 103 ms 26472 KB Ok
31 Correct 102 ms 26536 KB Ok
32 Correct 104 ms 26444 KB Ok
33 Correct 104 ms 26536 KB Ok
34 Correct 111 ms 26676 KB Ok
35 Correct 105 ms 26560 KB Ok
36 Correct 106 ms 26560 KB Ok
37 Correct 109 ms 26576 KB Ok
38 Correct 106 ms 26684 KB Ok
39 Correct 104 ms 26552 KB Ok
40 Correct 106 ms 26556 KB Ok
41 Correct 107 ms 26612 KB Ok
42 Correct 119 ms 26572 KB Ok
43 Correct 111 ms 26552 KB Ok
44 Correct 119 ms 26556 KB Ok
45 Correct 122 ms 26764 KB Ok
46 Correct 118 ms 26648 KB Ok
47 Correct 111 ms 26776 KB Ok
48 Correct 109 ms 26608 KB Ok
49 Correct 110 ms 26636 KB Ok
50 Correct 115 ms 26672 KB Ok
51 Correct 116 ms 26692 KB Ok
52 Correct 110 ms 26612 KB Ok
53 Correct 111 ms 26704 KB Ok
54 Correct 297 ms 28124 KB Ok
55 Correct 354 ms 28216 KB Ok
56 Correct 349 ms 28200 KB Ok
57 Correct 269 ms 27820 KB Ok
58 Correct 313 ms 28028 KB Ok
59 Correct 313 ms 28136 KB Ok
60 Correct 267 ms 27896 KB Ok
61 Correct 285 ms 27796 KB Ok
62 Correct 360 ms 28228 KB Ok
63 Correct 282 ms 27960 KB Ok
64 Correct 339 ms 28148 KB Ok
65 Correct 329 ms 28136 KB Ok
66 Correct 307 ms 28008 KB Ok
67 Correct 286 ms 27848 KB Ok
68 Correct 309 ms 28028 KB Ok
69 Correct 555 ms 31980 KB Ok
70 Correct 555 ms 33288 KB Ok
71 Correct 502 ms 31132 KB Ok
72 Correct 516 ms 32324 KB Ok
73 Correct 561 ms 31712 KB Ok
74 Correct 551 ms 30876 KB Ok
75 Correct 457 ms 30728 KB Ok
76 Correct 557 ms 33028 KB Ok
77 Correct 531 ms 30308 KB Ok
78 Correct 546 ms 32776 KB Ok
79 Correct 560 ms 32128 KB Ok
80 Correct 593 ms 31808 KB Ok
81 Correct 472 ms 32316 KB Ok
82 Correct 519 ms 31940 KB Ok
83 Correct 536 ms 30916 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 26436 KB Ok
2 Correct 114 ms 26540 KB Ok
3 Correct 104 ms 26540 KB Ok
4 Correct 105 ms 26472 KB Ok
5 Correct 113 ms 26540 KB Ok
6 Correct 105 ms 26540 KB Ok
7 Correct 105 ms 26436 KB Ok
8 Correct 104 ms 26516 KB Ok
9 Correct 111 ms 26496 KB Ok
10 Correct 111 ms 26436 KB Ok
11 Correct 103 ms 26536 KB Ok
12 Correct 105 ms 26536 KB Ok
13 Correct 109 ms 26536 KB Ok
14 Correct 108 ms 26536 KB Ok
15 Correct 108 ms 26536 KB Ok
16 Correct 102 ms 26492 KB Ok
17 Correct 102 ms 26480 KB Ok
18 Correct 108 ms 26572 KB Ok
19 Correct 131 ms 26992 KB Ok
20 Correct 111 ms 26684 KB Ok
21 Correct 126 ms 26824 KB Ok
22 Correct 115 ms 26664 KB Ok
23 Correct 51 ms 26536 KB Ok
24 Correct 105 ms 26600 KB Ok
25 Correct 109 ms 26540 KB Ok
26 Correct 106 ms 26544 KB Ok
27 Correct 104 ms 26544 KB Ok
28 Correct 116 ms 26540 KB Ok
29 Correct 107 ms 26564 KB Ok
30 Correct 103 ms 26472 KB Ok
31 Correct 102 ms 26536 KB Ok
32 Correct 104 ms 26444 KB Ok
33 Correct 104 ms 26536 KB Ok
34 Correct 103 ms 26564 KB Ok
35 Correct 102 ms 26540 KB Ok
36 Correct 108 ms 26540 KB Ok
37 Correct 109 ms 26492 KB Ok
38 Correct 113 ms 26496 KB Ok
39 Correct 340 ms 29400 KB Ok
40 Correct 304 ms 28780 KB Ok
41 Correct 542 ms 30920 KB Ok
42 Correct 412 ms 31352 KB Ok
43 Correct 278 ms 28284 KB Ok
44 Correct 440 ms 30232 KB Ok
45 Correct 111 ms 26676 KB Ok
46 Correct 105 ms 26560 KB Ok
47 Correct 106 ms 26560 KB Ok
48 Correct 109 ms 26576 KB Ok
49 Correct 106 ms 26684 KB Ok
50 Correct 104 ms 26552 KB Ok
51 Correct 106 ms 26556 KB Ok
52 Correct 107 ms 26612 KB Ok
53 Correct 119 ms 26572 KB Ok
54 Correct 111 ms 26552 KB Ok
55 Correct 119 ms 26556 KB Ok
56 Correct 122 ms 26764 KB Ok
57 Correct 118 ms 26648 KB Ok
58 Correct 111 ms 26776 KB Ok
59 Correct 109 ms 26608 KB Ok
60 Correct 110 ms 26636 KB Ok
61 Correct 115 ms 26672 KB Ok
62 Correct 116 ms 26692 KB Ok
63 Correct 110 ms 26612 KB Ok
64 Correct 111 ms 26704 KB Ok
65 Correct 297 ms 28124 KB Ok
66 Correct 354 ms 28216 KB Ok
67 Correct 349 ms 28200 KB Ok
68 Correct 269 ms 27820 KB Ok
69 Correct 313 ms 28028 KB Ok
70 Correct 313 ms 28136 KB Ok
71 Correct 267 ms 27896 KB Ok
72 Correct 285 ms 27796 KB Ok
73 Correct 360 ms 28228 KB Ok
74 Correct 282 ms 27960 KB Ok
75 Correct 339 ms 28148 KB Ok
76 Correct 329 ms 28136 KB Ok
77 Correct 307 ms 28008 KB Ok
78 Correct 286 ms 27848 KB Ok
79 Correct 309 ms 28028 KB Ok
80 Correct 555 ms 31980 KB Ok
81 Correct 555 ms 33288 KB Ok
82 Correct 502 ms 31132 KB Ok
83 Correct 516 ms 32324 KB Ok
84 Correct 561 ms 31712 KB Ok
85 Correct 551 ms 30876 KB Ok
86 Correct 457 ms 30728 KB Ok
87 Correct 557 ms 33028 KB Ok
88 Correct 531 ms 30308 KB Ok
89 Correct 546 ms 32776 KB Ok
90 Correct 560 ms 32128 KB Ok
91 Correct 593 ms 31808 KB Ok
92 Correct 472 ms 32316 KB Ok
93 Correct 519 ms 31940 KB Ok
94 Correct 536 ms 30916 KB Ok
95 Correct 692 ms 30396 KB Ok
96 Runtime error 47 ms 58800 KB Execution killed with signal 11
97 Halted 0 ms 0 KB -