oj.uz

Submission #1114125

# Submission time Handle Problem Language Result Execution time Memory
1114125 2024-11-18T08:17:00 Z vjudge1 Nice sequence (IZhO18_sequence) C++17
76 / 100
 702 ms 66472 KB 
//Dost SEFEROĞLU
#include <bits/stdc++.h>
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
using namespace std;
//#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>
const int MOD = 1e9+7,inf = 2e18;
const int N = 2e5+50,Q = 2e5+50;
const int LIM = 1000001;
vi edges[LIM];
bool vis[LIM],act[LIM];
int v[LIM];
struct DAG {
    int nd;
    bool cyclic = 0;
    void addedge(int a,int b) {
        edges[a].push_back(b);
    }
    void reset() {
        cyclic = 0;;
        for (int i = 0;i<=nd;i++) edges[i].clear(),vis[i] = 0,act[i] = 0;
    }
    void cyclecheck(int node) {
        if (vis[node]) return;
        if (cyclic) return;
        vis[node] = act[node] = 1;
        for (auto it : edges[node]) {
            if (act[it]) {
                cyclic = 1;
                return;
            }
            else if (!vis[it]) cyclecheck(it);
        }
        act[node] = 0;
    }
    void checkcycle() {
        for (int i = 0;i<=nd;i++) {
            cyclecheck(i);
            if (cyclic) break;
        }
    }
    int mex = 1;
    int dfs(int node) {
        if (vis[node]) return v[node];
        vis[node] = 1;
        for (auto it : edges[node]) dfs(it);
        return v[node] = mex++;
    }
    void solve() {
        for (int i = 0;i<=nd;i++) vis[i] = 0;
        for (int i = 0;i<=nd;i++) dfs(i);
    }
};
void solve() { 
    int n,m;
    cin >> n >> m;
    int l = 1;
    int r = LIM-1; // tune
    DAG D;
    while (l<=r) {
        int k = (l+r) >> 1;
        D.nd = k;
        for (int i = 1;i<=k;i++) {
            if (i >= m) D.addedge(i,i-m);
            if (i >= n) D.addedge(i-n,i);
        }
        D.checkcycle();
        if (!D.cyclic) l = k+1;
        else r = k-1;
        D.reset();
    }
    memset(v,-1,sizeof v);
    cout << r << '\n';
    D.nd = r;
    for (int i = 1;i<=r;i++) {
        if (i >= m) D.addedge(i,i-m);
        if (i >= n) D.addedge(i-n,i);
    } 
    D.solve();
    for (int i = 1;i<=r;i++) {
        cout << v[i]-v[i-1] << ' ';
    }
    cout << '\n'; 
}                    
                             
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    cin >> t; 
    while (t --> 0) solve();
}

Compilation message

sequence.cpp:12:29: warning: overflow in conversion from 'double' to 'int' changes value from '2.0e+18' to '2147483647' [-Woverflow]
   12 | const int MOD = 1e9+7,inf = 2e18;
      |                             ^~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 45392 KB Ok
2 Correct 76 ms 45272 KB Ok
3 Correct 80 ms 45336 KB Ok
4 Correct 81 ms 45404 KB Ok
5 Correct 78 ms 45384 KB Ok
6 Correct 76 ms 45384 KB Ok
7 Correct 77 ms 45384 KB Ok
8 Correct 76 ms 45384 KB Ok
9 Correct 79 ms 45452 KB Ok
10 Correct 86 ms 45384 KB Ok
11 Correct 78 ms 45384 KB Ok
12 Correct 76 ms 45384 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 45312 KB Ok
2 Correct 84 ms 45244 KB Ok
3 Correct 92 ms 45412 KB Ok
4 Correct 87 ms 45388 KB Ok
5 Correct 87 ms 45384 KB Ok
6 Correct 83 ms 45392 KB Ok
7 Correct 95 ms 45916 KB Ok
8 Correct 94 ms 45640 KB Ok
9 Correct 100 ms 46152 KB Ok
10 Correct 110 ms 45836 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 45384 KB Ok
2 Correct 86 ms 45384 KB Ok
3 Correct 88 ms 45384 KB Ok
4 Correct 91 ms 45384 KB Ok
5 Correct 90 ms 45356 KB Ok
6 Correct 81 ms 45392 KB Ok
7 Correct 86 ms 45384 KB Ok
8 Correct 85 ms 45304 KB Ok
9 Correct 97 ms 45384 KB Ok
10 Correct 88 ms 45364 KB Ok
11 Correct 88 ms 45384 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 45384 KB Ok
2 Correct 86 ms 45396 KB Ok
3 Correct 80 ms 45384 KB Ok
4 Correct 77 ms 45200 KB Ok
5 Correct 73 ms 45384 KB Ok
6 Correct 242 ms 54084 KB Ok
7 Correct 229 ms 54344 KB Ok
8 Correct 345 ms 57208 KB Ok
9 Correct 267 ms 55880 KB Ok
10 Correct 180 ms 50248 KB Ok
11 Correct 270 ms 55884 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 45392 KB Ok
2 Correct 76 ms 45272 KB Ok
3 Correct 80 ms 45336 KB Ok
4 Correct 81 ms 45404 KB Ok
5 Correct 78 ms 45384 KB Ok
6 Correct 76 ms 45384 KB Ok
7 Correct 77 ms 45384 KB Ok
8 Correct 76 ms 45384 KB Ok
9 Correct 79 ms 45452 KB Ok
10 Correct 86 ms 45384 KB Ok
11 Correct 78 ms 45384 KB Ok
12 Correct 76 ms 45384 KB Ok
13 Correct 58 ms 45384 KB Ok
14 Correct 86 ms 45384 KB Ok
15 Correct 88 ms 45384 KB Ok
16 Correct 91 ms 45384 KB Ok
17 Correct 90 ms 45356 KB Ok
18 Correct 81 ms 45392 KB Ok
19 Correct 86 ms 45384 KB Ok
20 Correct 85 ms 45304 KB Ok
21 Correct 97 ms 45384 KB Ok
22 Correct 88 ms 45364 KB Ok
23 Correct 88 ms 45384 KB Ok
24 Correct 76 ms 45384 KB Ok
25 Correct 78 ms 45284 KB Ok
26 Correct 82 ms 45472 KB Ok
27 Correct 80 ms 45384 KB Ok
28 Correct 91 ms 45384 KB Ok
29 Correct 84 ms 45400 KB Ok
30 Correct 82 ms 45436 KB Ok
31 Correct 85 ms 45472 KB Ok
32 Correct 85 ms 45380 KB Ok
33 Correct 84 ms 45384 KB Ok
34 Correct 89 ms 45640 KB Ok
35 Correct 89 ms 45652 KB Ok
36 Correct 96 ms 45640 KB Ok
37 Correct 96 ms 45636 KB Ok
38 Correct 97 ms 45536 KB Ok
39 Correct 99 ms 45700 KB Ok
40 Correct 99 ms 45640 KB Ok
41 Correct 93 ms 45652 KB Ok
42 Correct 88 ms 45516 KB Ok
43 Correct 88 ms 45648 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 45392 KB Ok
2 Correct 76 ms 45272 KB Ok
3 Correct 80 ms 45336 KB Ok
4 Correct 81 ms 45404 KB Ok
5 Correct 78 ms 45384 KB Ok
6 Correct 76 ms 45384 KB Ok
7 Correct 77 ms 45384 KB Ok
8 Correct 76 ms 45384 KB Ok
9 Correct 79 ms 45452 KB Ok
10 Correct 86 ms 45384 KB Ok
11 Correct 78 ms 45384 KB Ok
12 Correct 76 ms 45384 KB Ok
13 Correct 89 ms 45312 KB Ok
14 Correct 84 ms 45244 KB Ok
15 Correct 92 ms 45412 KB Ok
16 Correct 87 ms 45388 KB Ok
17 Correct 87 ms 45384 KB Ok
18 Correct 83 ms 45392 KB Ok
19 Correct 95 ms 45916 KB Ok
20 Correct 94 ms 45640 KB Ok
21 Correct 100 ms 46152 KB Ok
22 Correct 110 ms 45836 KB Ok
23 Correct 58 ms 45384 KB Ok
24 Correct 86 ms 45384 KB Ok
25 Correct 88 ms 45384 KB Ok
26 Correct 91 ms 45384 KB Ok
27 Correct 90 ms 45356 KB Ok
28 Correct 81 ms 45392 KB Ok
29 Correct 86 ms 45384 KB Ok
30 Correct 85 ms 45304 KB Ok
31 Correct 97 ms 45384 KB Ok
32 Correct 88 ms 45364 KB Ok
33 Correct 88 ms 45384 KB Ok
34 Correct 76 ms 45384 KB Ok
35 Correct 78 ms 45284 KB Ok
36 Correct 82 ms 45472 KB Ok
37 Correct 80 ms 45384 KB Ok
38 Correct 91 ms 45384 KB Ok
39 Correct 84 ms 45400 KB Ok
40 Correct 82 ms 45436 KB Ok
41 Correct 85 ms 45472 KB Ok
42 Correct 85 ms 45380 KB Ok
43 Correct 84 ms 45384 KB Ok
44 Correct 89 ms 45640 KB Ok
45 Correct 89 ms 45652 KB Ok
46 Correct 96 ms 45640 KB Ok
47 Correct 96 ms 45636 KB Ok
48 Correct 97 ms 45536 KB Ok
49 Correct 99 ms 45700 KB Ok
50 Correct 99 ms 45640 KB Ok
51 Correct 93 ms 45652 KB Ok
52 Correct 88 ms 45516 KB Ok
53 Correct 88 ms 45648 KB Ok
54 Correct 171 ms 47040 KB Ok
55 Correct 192 ms 47356 KB Ok
56 Correct 190 ms 47360 KB Ok
57 Correct 164 ms 46660 KB Ok
58 Correct 157 ms 46920 KB Ok
59 Correct 145 ms 46604 KB Ok
60 Correct 143 ms 46664 KB Ok
61 Correct 143 ms 46664 KB Ok
62 Correct 170 ms 47172 KB Ok
63 Correct 168 ms 46920 KB Ok
64 Correct 190 ms 47344 KB Ok
65 Correct 166 ms 46880 KB Ok
66 Correct 163 ms 46928 KB Ok
67 Correct 153 ms 46664 KB Ok
68 Correct 170 ms 46816 KB Ok
69 Correct 362 ms 54856 KB Ok
70 Correct 415 ms 55524 KB Ok
71 Correct 324 ms 54904 KB Ok
72 Correct 391 ms 54784 KB Ok
73 Correct 353 ms 54856 KB Ok
74 Correct 340 ms 54600 KB Ok
75 Correct 338 ms 54344 KB Ok
76 Correct 379 ms 55112 KB Ok
77 Correct 323 ms 54344 KB Ok
78 Correct 385 ms 54888 KB Ok
79 Correct 375 ms 55112 KB Ok
80 Correct 377 ms 55224 KB Ok
81 Correct 392 ms 55024 KB Ok
82 Correct 372 ms 54856 KB Ok
83 Correct 344 ms 54536 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 45392 KB Ok
2 Correct 76 ms 45272 KB Ok
3 Correct 80 ms 45336 KB Ok
4 Correct 81 ms 45404 KB Ok
5 Correct 78 ms 45384 KB Ok
6 Correct 76 ms 45384 KB Ok
7 Correct 77 ms 45384 KB Ok
8 Correct 76 ms 45384 KB Ok
9 Correct 79 ms 45452 KB Ok
10 Correct 86 ms 45384 KB Ok
11 Correct 78 ms 45384 KB Ok
12 Correct 76 ms 45384 KB Ok
13 Correct 89 ms 45312 KB Ok
14 Correct 84 ms 45244 KB Ok
15 Correct 92 ms 45412 KB Ok
16 Correct 87 ms 45388 KB Ok
17 Correct 87 ms 45384 KB Ok
18 Correct 83 ms 45392 KB Ok
19 Correct 95 ms 45916 KB Ok
20 Correct 94 ms 45640 KB Ok
21 Correct 100 ms 46152 KB Ok
22 Correct 110 ms 45836 KB Ok
23 Correct 58 ms 45384 KB Ok
24 Correct 86 ms 45384 KB Ok
25 Correct 88 ms 45384 KB Ok
26 Correct 91 ms 45384 KB Ok
27 Correct 90 ms 45356 KB Ok
28 Correct 81 ms 45392 KB Ok
29 Correct 86 ms 45384 KB Ok
30 Correct 85 ms 45304 KB Ok
31 Correct 97 ms 45384 KB Ok
32 Correct 88 ms 45364 KB Ok
33 Correct 88 ms 45384 KB Ok
34 Correct 89 ms 45384 KB Ok
35 Correct 86 ms 45396 KB Ok
36 Correct 80 ms 45384 KB Ok
37 Correct 77 ms 45200 KB Ok
38 Correct 73 ms 45384 KB Ok
39 Correct 242 ms 54084 KB Ok
40 Correct 229 ms 54344 KB Ok
41 Correct 345 ms 57208 KB Ok
42 Correct 267 ms 55880 KB Ok
43 Correct 180 ms 50248 KB Ok
44 Correct 270 ms 55884 KB Ok
45 Correct 76 ms 45384 KB Ok
46 Correct 78 ms 45284 KB Ok
47 Correct 82 ms 45472 KB Ok
48 Correct 80 ms 45384 KB Ok
49 Correct 91 ms 45384 KB Ok
50 Correct 84 ms 45400 KB Ok
51 Correct 82 ms 45436 KB Ok
52 Correct 85 ms 45472 KB Ok
53 Correct 85 ms 45380 KB Ok
54 Correct 84 ms 45384 KB Ok
55 Correct 89 ms 45640 KB Ok
56 Correct 89 ms 45652 KB Ok
57 Correct 96 ms 45640 KB Ok
58 Correct 96 ms 45636 KB Ok
59 Correct 97 ms 45536 KB Ok
60 Correct 99 ms 45700 KB Ok
61 Correct 99 ms 45640 KB Ok
62 Correct 93 ms 45652 KB Ok
63 Correct 88 ms 45516 KB Ok
64 Correct 88 ms 45648 KB Ok
65 Correct 171 ms 47040 KB Ok
66 Correct 192 ms 47356 KB Ok
67 Correct 190 ms 47360 KB Ok
68 Correct 164 ms 46660 KB Ok
69 Correct 157 ms 46920 KB Ok
70 Correct 145 ms 46604 KB Ok
71 Correct 143 ms 46664 KB Ok
72 Correct 143 ms 46664 KB Ok
73 Correct 170 ms 47172 KB Ok
74 Correct 168 ms 46920 KB Ok
75 Correct 190 ms 47344 KB Ok
76 Correct 166 ms 46880 KB Ok
77 Correct 163 ms 46928 KB Ok
78 Correct 153 ms 46664 KB Ok
79 Correct 170 ms 46816 KB Ok
80 Correct 362 ms 54856 KB Ok
81 Correct 415 ms 55524 KB Ok
82 Correct 324 ms 54904 KB Ok
83 Correct 391 ms 54784 KB Ok
84 Correct 353 ms 54856 KB Ok
85 Correct 340 ms 54600 KB Ok
86 Correct 338 ms 54344 KB Ok
87 Correct 379 ms 55112 KB Ok
88 Correct 323 ms 54344 KB Ok
89 Correct 385 ms 54888 KB Ok
90 Correct 375 ms 55112 KB Ok
91 Correct 377 ms 55224 KB Ok
92 Correct 392 ms 55024 KB Ok
93 Correct 372 ms 54856 KB Ok
94 Correct 344 ms 54536 KB Ok
95 Correct 311 ms 49748 KB Ok
96 Incorrect 702 ms 66472 KB there is incorrect sequence
97 Halted 0 ms 0 KB -