oj.uz

Submission #513595

# Submission time Handle Problem Language Result Execution time Memory
513595 2022-01-17T09:43:31 Z Killer2501 Nice sequence (IZhO18_sequence) C++14
76 / 100
 2000 ms 54156 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 = 5e5+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 = 4e5, 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 98 ms 35548 KB Ok
2 Correct 105 ms 35536 KB Ok
3 Correct 90 ms 35536 KB Ok
4 Correct 92 ms 35536 KB Ok
5 Correct 92 ms 35460 KB Ok
6 Correct 93 ms 35532 KB Ok
7 Correct 107 ms 35456 KB Ok
8 Correct 82 ms 35524 KB Ok
9 Correct 91 ms 35536 KB Ok
10 Correct 90 ms 35536 KB Ok
11 Correct 92 ms 35528 KB Ok
12 Correct 83 ms 35452 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 35532 KB Ok
2 Correct 100 ms 35540 KB Ok
3 Correct 98 ms 35536 KB Ok
4 Correct 93 ms 35536 KB Ok
5 Correct 104 ms 35536 KB Ok
6 Correct 91 ms 35560 KB Ok
7 Correct 113 ms 35872 KB Ok
8 Correct 105 ms 35596 KB Ok
9 Correct 126 ms 35908 KB Ok
10 Correct 114 ms 35692 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 35536 KB Ok
2 Correct 93 ms 35516 KB Ok
3 Correct 106 ms 35536 KB Ok
4 Correct 107 ms 35456 KB Ok
5 Correct 112 ms 35528 KB Ok
6 Correct 98 ms 35536 KB Ok
7 Correct 89 ms 35492 KB Ok
8 Correct 100 ms 35536 KB Ok
9 Correct 101 ms 35532 KB Ok
10 Correct 95 ms 35536 KB Ok
11 Correct 91 ms 35532 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 35508 KB Ok
2 Correct 100 ms 35664 KB Ok
3 Correct 95 ms 35536 KB Ok
4 Correct 95 ms 35600 KB Ok
5 Correct 88 ms 35536 KB Ok
6 Correct 333 ms 38416 KB Ok
7 Correct 291 ms 37792 KB Ok
8 Correct 528 ms 39716 KB Ok
9 Correct 430 ms 40308 KB Ok
10 Correct 319 ms 37168 KB Ok
11 Correct 430 ms 39264 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 35548 KB Ok
2 Correct 105 ms 35536 KB Ok
3 Correct 90 ms 35536 KB Ok
4 Correct 92 ms 35536 KB Ok
5 Correct 92 ms 35460 KB Ok
6 Correct 93 ms 35532 KB Ok
7 Correct 107 ms 35456 KB Ok
8 Correct 82 ms 35524 KB Ok
9 Correct 91 ms 35536 KB Ok
10 Correct 90 ms 35536 KB Ok
11 Correct 92 ms 35528 KB Ok
12 Correct 83 ms 35452 KB Ok
13 Correct 53 ms 35536 KB Ok
14 Correct 93 ms 35516 KB Ok
15 Correct 106 ms 35536 KB Ok
16 Correct 107 ms 35456 KB Ok
17 Correct 112 ms 35528 KB Ok
18 Correct 98 ms 35536 KB Ok
19 Correct 89 ms 35492 KB Ok
20 Correct 100 ms 35536 KB Ok
21 Correct 101 ms 35532 KB Ok
22 Correct 95 ms 35536 KB Ok
23 Correct 91 ms 35532 KB Ok
24 Correct 94 ms 35560 KB Ok
25 Correct 93 ms 35492 KB Ok
26 Correct 94 ms 35684 KB Ok
27 Correct 93 ms 35568 KB Ok
28 Correct 92 ms 35536 KB Ok
29 Correct 96 ms 35548 KB Ok
30 Correct 110 ms 35524 KB Ok
31 Correct 95 ms 35564 KB Ok
32 Correct 99 ms 35580 KB Ok
33 Correct 104 ms 35556 KB Ok
34 Correct 118 ms 35712 KB Ok
35 Correct 92 ms 35664 KB Ok
36 Correct 102 ms 35620 KB Ok
37 Correct 100 ms 35852 KB Ok
38 Correct 110 ms 35688 KB Ok
39 Correct 99 ms 35684 KB Ok
40 Correct 98 ms 35580 KB Ok
41 Correct 106 ms 35632 KB Ok
42 Correct 96 ms 35664 KB Ok
43 Correct 101 ms 35688 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 35548 KB Ok
2 Correct 105 ms 35536 KB Ok
3 Correct 90 ms 35536 KB Ok
4 Correct 92 ms 35536 KB Ok
5 Correct 92 ms 35460 KB Ok
6 Correct 93 ms 35532 KB Ok
7 Correct 107 ms 35456 KB Ok
8 Correct 82 ms 35524 KB Ok
9 Correct 91 ms 35536 KB Ok
10 Correct 90 ms 35536 KB Ok
11 Correct 92 ms 35528 KB Ok
12 Correct 83 ms 35452 KB Ok
13 Correct 94 ms 35532 KB Ok
14 Correct 100 ms 35540 KB Ok
15 Correct 98 ms 35536 KB Ok
16 Correct 93 ms 35536 KB Ok
17 Correct 104 ms 35536 KB Ok
18 Correct 91 ms 35560 KB Ok
19 Correct 113 ms 35872 KB Ok
20 Correct 105 ms 35596 KB Ok
21 Correct 126 ms 35908 KB Ok
22 Correct 114 ms 35692 KB Ok
23 Correct 53 ms 35536 KB Ok
24 Correct 93 ms 35516 KB Ok
25 Correct 106 ms 35536 KB Ok
26 Correct 107 ms 35456 KB Ok
27 Correct 112 ms 35528 KB Ok
28 Correct 98 ms 35536 KB Ok
29 Correct 89 ms 35492 KB Ok
30 Correct 100 ms 35536 KB Ok
31 Correct 101 ms 35532 KB Ok
32 Correct 95 ms 35536 KB Ok
33 Correct 91 ms 35532 KB Ok
34 Correct 94 ms 35560 KB Ok
35 Correct 93 ms 35492 KB Ok
36 Correct 94 ms 35684 KB Ok
37 Correct 93 ms 35568 KB Ok
38 Correct 92 ms 35536 KB Ok
39 Correct 96 ms 35548 KB Ok
40 Correct 110 ms 35524 KB Ok
41 Correct 95 ms 35564 KB Ok
42 Correct 99 ms 35580 KB Ok
43 Correct 104 ms 35556 KB Ok
44 Correct 118 ms 35712 KB Ok
45 Correct 92 ms 35664 KB Ok
46 Correct 102 ms 35620 KB Ok
47 Correct 100 ms 35852 KB Ok
48 Correct 110 ms 35688 KB Ok
49 Correct 99 ms 35684 KB Ok
50 Correct 98 ms 35580 KB Ok
51 Correct 106 ms 35632 KB Ok
52 Correct 96 ms 35664 KB Ok
53 Correct 101 ms 35688 KB Ok
54 Correct 286 ms 36940 KB Ok
55 Correct 351 ms 37240 KB Ok
56 Correct 352 ms 37172 KB Ok
57 Correct 273 ms 36852 KB Ok
58 Correct 308 ms 37084 KB Ok
59 Correct 285 ms 37072 KB Ok
60 Correct 280 ms 36852 KB Ok
61 Correct 279 ms 36852 KB Ok
62 Correct 366 ms 37332 KB Ok
63 Correct 285 ms 36912 KB Ok
64 Correct 379 ms 37096 KB Ok
65 Correct 330 ms 37128 KB Ok
66 Correct 299 ms 36960 KB Ok
67 Correct 256 ms 36812 KB Ok
68 Correct 294 ms 37004 KB Ok
69 Correct 801 ms 40968 KB Ok
70 Correct 626 ms 42272 KB Ok
71 Correct 604 ms 40092 KB Ok
72 Correct 654 ms 41268 KB Ok
73 Correct 581 ms 40656 KB Ok
74 Correct 537 ms 39732 KB Ok
75 Correct 556 ms 39752 KB Ok
76 Correct 730 ms 41988 KB Ok
77 Correct 558 ms 39372 KB Ok
78 Correct 702 ms 41652 KB Ok
79 Correct 641 ms 41096 KB Ok
80 Correct 583 ms 40876 KB Ok
81 Correct 542 ms 41328 KB Ok
82 Correct 658 ms 40968 KB Ok
83 Correct 548 ms 39892 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 35548 KB Ok
2 Correct 105 ms 35536 KB Ok
3 Correct 90 ms 35536 KB Ok
4 Correct 92 ms 35536 KB Ok
5 Correct 92 ms 35460 KB Ok
6 Correct 93 ms 35532 KB Ok
7 Correct 107 ms 35456 KB Ok
8 Correct 82 ms 35524 KB Ok
9 Correct 91 ms 35536 KB Ok
10 Correct 90 ms 35536 KB Ok
11 Correct 92 ms 35528 KB Ok
12 Correct 83 ms 35452 KB Ok
13 Correct 94 ms 35532 KB Ok
14 Correct 100 ms 35540 KB Ok
15 Correct 98 ms 35536 KB Ok
16 Correct 93 ms 35536 KB Ok
17 Correct 104 ms 35536 KB Ok
18 Correct 91 ms 35560 KB Ok
19 Correct 113 ms 35872 KB Ok
20 Correct 105 ms 35596 KB Ok
21 Correct 126 ms 35908 KB Ok
22 Correct 114 ms 35692 KB Ok
23 Correct 53 ms 35536 KB Ok
24 Correct 93 ms 35516 KB Ok
25 Correct 106 ms 35536 KB Ok
26 Correct 107 ms 35456 KB Ok
27 Correct 112 ms 35528 KB Ok
28 Correct 98 ms 35536 KB Ok
29 Correct 89 ms 35492 KB Ok
30 Correct 100 ms 35536 KB Ok
31 Correct 101 ms 35532 KB Ok
32 Correct 95 ms 35536 KB Ok
33 Correct 91 ms 35532 KB Ok
34 Correct 84 ms 35508 KB Ok
35 Correct 100 ms 35664 KB Ok
36 Correct 95 ms 35536 KB Ok
37 Correct 95 ms 35600 KB Ok
38 Correct 88 ms 35536 KB Ok
39 Correct 333 ms 38416 KB Ok
40 Correct 291 ms 37792 KB Ok
41 Correct 528 ms 39716 KB Ok
42 Correct 430 ms 40308 KB Ok
43 Correct 319 ms 37168 KB Ok
44 Correct 430 ms 39264 KB Ok
45 Correct 94 ms 35560 KB Ok
46 Correct 93 ms 35492 KB Ok
47 Correct 94 ms 35684 KB Ok
48 Correct 93 ms 35568 KB Ok
49 Correct 92 ms 35536 KB Ok
50 Correct 96 ms 35548 KB Ok
51 Correct 110 ms 35524 KB Ok
52 Correct 95 ms 35564 KB Ok
53 Correct 99 ms 35580 KB Ok
54 Correct 104 ms 35556 KB Ok
55 Correct 118 ms 35712 KB Ok
56 Correct 92 ms 35664 KB Ok
57 Correct 102 ms 35620 KB Ok
58 Correct 100 ms 35852 KB Ok
59 Correct 110 ms 35688 KB Ok
60 Correct 99 ms 35684 KB Ok
61 Correct 98 ms 35580 KB Ok
62 Correct 106 ms 35632 KB Ok
63 Correct 96 ms 35664 KB Ok
64 Correct 101 ms 35688 KB Ok
65 Correct 286 ms 36940 KB Ok
66 Correct 351 ms 37240 KB Ok
67 Correct 352 ms 37172 KB Ok
68 Correct 273 ms 36852 KB Ok
69 Correct 308 ms 37084 KB Ok
70 Correct 285 ms 37072 KB Ok
71 Correct 280 ms 36852 KB Ok
72 Correct 279 ms 36852 KB Ok
73 Correct 366 ms 37332 KB Ok
74 Correct 285 ms 36912 KB Ok
75 Correct 379 ms 37096 KB Ok
76 Correct 330 ms 37128 KB Ok
77 Correct 299 ms 36960 KB Ok
78 Correct 256 ms 36812 KB Ok
79 Correct 294 ms 37004 KB Ok
80 Correct 801 ms 40968 KB Ok
81 Correct 626 ms 42272 KB Ok
82 Correct 604 ms 40092 KB Ok
83 Correct 654 ms 41268 KB Ok
84 Correct 581 ms 40656 KB Ok
85 Correct 537 ms 39732 KB Ok
86 Correct 556 ms 39752 KB Ok
87 Correct 730 ms 41988 KB Ok
88 Correct 558 ms 39372 KB Ok
89 Correct 702 ms 41652 KB Ok
90 Correct 641 ms 41096 KB Ok
91 Correct 583 ms 40876 KB Ok
92 Correct 542 ms 41328 KB Ok
93 Correct 658 ms 40968 KB Ok
94 Correct 548 ms 39892 KB Ok
95 Correct 705 ms 43216 KB Ok
96 Correct 1136 ms 47644 KB Ok
97 Correct 1107 ms 44756 KB Ok
98 Correct 786 ms 45484 KB Ok
99 Correct 931 ms 43940 KB Ok
100 Correct 1084 ms 43964 KB Ok
101 Correct 976 ms 46060 KB Ok
102 Correct 922 ms 43860 KB Ok
103 Correct 956 ms 45952 KB Ok
104 Correct 1146 ms 46916 KB Ok
105 Correct 1145 ms 47128 KB Ok
106 Correct 849 ms 46680 KB Ok
107 Correct 976 ms 46188 KB Ok
108 Correct 1075 ms 46572 KB Ok
109 Correct 943 ms 47688 KB Ok
110 Execution timed out 2078 ms 54156 KB Time limit exceeded
111 Halted 0 ms 0 KB -