oj.uz

Submission #1114121

# Submission time Handle Problem Language Result Execution time Memory
1114121 2024-11-18T08:14:24 Z vjudge1 Nice sequence (IZhO18_sequence) C++17
76 / 100
 2000 ms 121568 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 = 2000001;
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++) {
        assert(v[i] != v[i-1]);
        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 188 ms 89400 KB Ok
2 Correct 206 ms 89672 KB Ok
3 Correct 193 ms 88392 KB Ok
4 Correct 192 ms 88372 KB Ok
5 Correct 168 ms 88300 KB Ok
6 Correct 192 ms 88512 KB Ok
7 Correct 162 ms 89484 KB Ok
8 Correct 168 ms 89340 KB Ok
9 Correct 173 ms 89496 KB Ok
10 Correct 196 ms 89416 KB Ok
11 Correct 164 ms 89416 KB Ok
12 Correct 162 ms 89420 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 89416 KB Ok
2 Correct 191 ms 89384 KB Ok
3 Correct 197 ms 89416 KB Ok
4 Correct 207 ms 89424 KB Ok
5 Correct 214 ms 89424 KB Ok
6 Correct 184 ms 89416 KB Ok
7 Correct 222 ms 90096 KB Ok
8 Correct 209 ms 89672 KB Ok
9 Correct 202 ms 90184 KB Ok
10 Correct 203 ms 89928 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 89608 KB Ok
2 Correct 186 ms 89416 KB Ok
3 Correct 207 ms 89420 KB Ok
4 Correct 190 ms 89416 KB Ok
5 Correct 189 ms 89420 KB Ok
6 Correct 193 ms 89304 KB Ok
7 Correct 190 ms 89416 KB Ok
8 Correct 208 ms 89420 KB Ok
9 Correct 188 ms 89416 KB Ok
10 Correct 190 ms 89416 KB Ok
11 Correct 204 ms 89340 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 89344 KB Ok
2 Correct 199 ms 89416 KB Ok
3 Correct 180 ms 89352 KB Ok
4 Correct 162 ms 89372 KB Ok
5 Correct 180 ms 89416 KB Ok
6 Correct 378 ms 98120 KB Ok
7 Correct 346 ms 98376 KB Ok
8 Correct 518 ms 101448 KB Ok
9 Correct 420 ms 99912 KB Ok
10 Correct 308 ms 94280 KB Ok
11 Correct 431 ms 99916 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 89400 KB Ok
2 Correct 206 ms 89672 KB Ok
3 Correct 193 ms 88392 KB Ok
4 Correct 192 ms 88372 KB Ok
5 Correct 168 ms 88300 KB Ok
6 Correct 192 ms 88512 KB Ok
7 Correct 162 ms 89484 KB Ok
8 Correct 168 ms 89340 KB Ok
9 Correct 173 ms 89496 KB Ok
10 Correct 196 ms 89416 KB Ok
11 Correct 164 ms 89416 KB Ok
12 Correct 162 ms 89420 KB Ok
13 Correct 124 ms 89608 KB Ok
14 Correct 186 ms 89416 KB Ok
15 Correct 207 ms 89420 KB Ok
16 Correct 190 ms 89416 KB Ok
17 Correct 189 ms 89420 KB Ok
18 Correct 193 ms 89304 KB Ok
19 Correct 190 ms 89416 KB Ok
20 Correct 208 ms 89420 KB Ok
21 Correct 188 ms 89416 KB Ok
22 Correct 190 ms 89416 KB Ok
23 Correct 204 ms 89340 KB Ok
24 Correct 167 ms 89420 KB Ok
25 Correct 171 ms 89356 KB Ok
26 Correct 196 ms 89416 KB Ok
27 Correct 165 ms 89416 KB Ok
28 Correct 165 ms 89520 KB Ok
29 Correct 168 ms 89536 KB Ok
30 Correct 178 ms 89672 KB Ok
31 Correct 173 ms 89312 KB Ok
32 Correct 169 ms 89416 KB Ok
33 Correct 202 ms 89416 KB Ok
34 Correct 190 ms 89672 KB Ok
35 Correct 193 ms 89672 KB Ok
36 Correct 208 ms 89672 KB Ok
37 Correct 197 ms 89588 KB Ok
38 Correct 184 ms 89672 KB Ok
39 Correct 190 ms 89672 KB Ok
40 Correct 207 ms 89672 KB Ok
41 Correct 186 ms 89672 KB Ok
42 Correct 179 ms 89672 KB Ok
43 Correct 187 ms 89600 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 89400 KB Ok
2 Correct 206 ms 89672 KB Ok
3 Correct 193 ms 88392 KB Ok
4 Correct 192 ms 88372 KB Ok
5 Correct 168 ms 88300 KB Ok
6 Correct 192 ms 88512 KB Ok
7 Correct 162 ms 89484 KB Ok
8 Correct 168 ms 89340 KB Ok
9 Correct 173 ms 89496 KB Ok
10 Correct 196 ms 89416 KB Ok
11 Correct 164 ms 89416 KB Ok
12 Correct 162 ms 89420 KB Ok
13 Correct 193 ms 89416 KB Ok
14 Correct 191 ms 89384 KB Ok
15 Correct 197 ms 89416 KB Ok
16 Correct 207 ms 89424 KB Ok
17 Correct 214 ms 89424 KB Ok
18 Correct 184 ms 89416 KB Ok
19 Correct 222 ms 90096 KB Ok
20 Correct 209 ms 89672 KB Ok
21 Correct 202 ms 90184 KB Ok
22 Correct 203 ms 89928 KB Ok
23 Correct 124 ms 89608 KB Ok
24 Correct 186 ms 89416 KB Ok
25 Correct 207 ms 89420 KB Ok
26 Correct 190 ms 89416 KB Ok
27 Correct 189 ms 89420 KB Ok
28 Correct 193 ms 89304 KB Ok
29 Correct 190 ms 89416 KB Ok
30 Correct 208 ms 89420 KB Ok
31 Correct 188 ms 89416 KB Ok
32 Correct 190 ms 89416 KB Ok
33 Correct 204 ms 89340 KB Ok
34 Correct 167 ms 89420 KB Ok
35 Correct 171 ms 89356 KB Ok
36 Correct 196 ms 89416 KB Ok
37 Correct 165 ms 89416 KB Ok
38 Correct 165 ms 89520 KB Ok
39 Correct 168 ms 89536 KB Ok
40 Correct 178 ms 89672 KB Ok
41 Correct 173 ms 89312 KB Ok
42 Correct 169 ms 89416 KB Ok
43 Correct 202 ms 89416 KB Ok
44 Correct 190 ms 89672 KB Ok
45 Correct 193 ms 89672 KB Ok
46 Correct 208 ms 89672 KB Ok
47 Correct 197 ms 89588 KB Ok
48 Correct 184 ms 89672 KB Ok
49 Correct 190 ms 89672 KB Ok
50 Correct 207 ms 89672 KB Ok
51 Correct 186 ms 89672 KB Ok
52 Correct 179 ms 89672 KB Ok
53 Correct 187 ms 89600 KB Ok
54 Correct 270 ms 90952 KB Ok
55 Correct 292 ms 91476 KB Ok
56 Correct 293 ms 91324 KB Ok
57 Correct 254 ms 90696 KB Ok
58 Correct 280 ms 90952 KB Ok
59 Correct 258 ms 90804 KB Ok
60 Correct 256 ms 90696 KB Ok
61 Correct 254 ms 90560 KB Ok
62 Correct 300 ms 91208 KB Ok
63 Correct 280 ms 90860 KB Ok
64 Correct 291 ms 91464 KB Ok
65 Correct 288 ms 90948 KB Ok
66 Correct 280 ms 90952 KB Ok
67 Correct 250 ms 90808 KB Ok
68 Correct 269 ms 90964 KB Ok
69 Correct 523 ms 98796 KB Ok
70 Correct 577 ms 99368 KB Ok
71 Correct 472 ms 98888 KB Ok
72 Correct 541 ms 98932 KB Ok
73 Correct 492 ms 98892 KB Ok
74 Correct 463 ms 98888 KB Ok
75 Correct 509 ms 98460 KB Ok
76 Correct 560 ms 99320 KB Ok
77 Correct 440 ms 98376 KB Ok
78 Correct 513 ms 98992 KB Ok
79 Correct 485 ms 99144 KB Ok
80 Correct 453 ms 99276 KB Ok
81 Correct 488 ms 98984 KB Ok
82 Correct 472 ms 99104 KB Ok
83 Correct 480 ms 98592 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 89400 KB Ok
2 Correct 206 ms 89672 KB Ok
3 Correct 193 ms 88392 KB Ok
4 Correct 192 ms 88372 KB Ok
5 Correct 168 ms 88300 KB Ok
6 Correct 192 ms 88512 KB Ok
7 Correct 162 ms 89484 KB Ok
8 Correct 168 ms 89340 KB Ok
9 Correct 173 ms 89496 KB Ok
10 Correct 196 ms 89416 KB Ok
11 Correct 164 ms 89416 KB Ok
12 Correct 162 ms 89420 KB Ok
13 Correct 193 ms 89416 KB Ok
14 Correct 191 ms 89384 KB Ok
15 Correct 197 ms 89416 KB Ok
16 Correct 207 ms 89424 KB Ok
17 Correct 214 ms 89424 KB Ok
18 Correct 184 ms 89416 KB Ok
19 Correct 222 ms 90096 KB Ok
20 Correct 209 ms 89672 KB Ok
21 Correct 202 ms 90184 KB Ok
22 Correct 203 ms 89928 KB Ok
23 Correct 124 ms 89608 KB Ok
24 Correct 186 ms 89416 KB Ok
25 Correct 207 ms 89420 KB Ok
26 Correct 190 ms 89416 KB Ok
27 Correct 189 ms 89420 KB Ok
28 Correct 193 ms 89304 KB Ok
29 Correct 190 ms 89416 KB Ok
30 Correct 208 ms 89420 KB Ok
31 Correct 188 ms 89416 KB Ok
32 Correct 190 ms 89416 KB Ok
33 Correct 204 ms 89340 KB Ok
34 Correct 184 ms 89344 KB Ok
35 Correct 199 ms 89416 KB Ok
36 Correct 180 ms 89352 KB Ok
37 Correct 162 ms 89372 KB Ok
38 Correct 180 ms 89416 KB Ok
39 Correct 378 ms 98120 KB Ok
40 Correct 346 ms 98376 KB Ok
41 Correct 518 ms 101448 KB Ok
42 Correct 420 ms 99912 KB Ok
43 Correct 308 ms 94280 KB Ok
44 Correct 431 ms 99916 KB Ok
45 Correct 167 ms 89420 KB Ok
46 Correct 171 ms 89356 KB Ok
47 Correct 196 ms 89416 KB Ok
48 Correct 165 ms 89416 KB Ok
49 Correct 165 ms 89520 KB Ok
50 Correct 168 ms 89536 KB Ok
51 Correct 178 ms 89672 KB Ok
52 Correct 173 ms 89312 KB Ok
53 Correct 169 ms 89416 KB Ok
54 Correct 202 ms 89416 KB Ok
55 Correct 190 ms 89672 KB Ok
56 Correct 193 ms 89672 KB Ok
57 Correct 208 ms 89672 KB Ok
58 Correct 197 ms 89588 KB Ok
59 Correct 184 ms 89672 KB Ok
60 Correct 190 ms 89672 KB Ok
61 Correct 207 ms 89672 KB Ok
62 Correct 186 ms 89672 KB Ok
63 Correct 179 ms 89672 KB Ok
64 Correct 187 ms 89600 KB Ok
65 Correct 270 ms 90952 KB Ok
66 Correct 292 ms 91476 KB Ok
67 Correct 293 ms 91324 KB Ok
68 Correct 254 ms 90696 KB Ok
69 Correct 280 ms 90952 KB Ok
70 Correct 258 ms 90804 KB Ok
71 Correct 256 ms 90696 KB Ok
72 Correct 254 ms 90560 KB Ok
73 Correct 300 ms 91208 KB Ok
74 Correct 280 ms 90860 KB Ok
75 Correct 291 ms 91464 KB Ok
76 Correct 288 ms 90948 KB Ok
77 Correct 280 ms 90952 KB Ok
78 Correct 250 ms 90808 KB Ok
79 Correct 269 ms 90964 KB Ok
80 Correct 523 ms 98796 KB Ok
81 Correct 577 ms 99368 KB Ok
82 Correct 472 ms 98888 KB Ok
83 Correct 541 ms 98932 KB Ok
84 Correct 492 ms 98892 KB Ok
85 Correct 463 ms 98888 KB Ok
86 Correct 509 ms 98460 KB Ok
87 Correct 560 ms 99320 KB Ok
88 Correct 440 ms 98376 KB Ok
89 Correct 513 ms 98992 KB Ok
90 Correct 485 ms 99144 KB Ok
91 Correct 453 ms 99276 KB Ok
92 Correct 488 ms 98984 KB Ok
93 Correct 472 ms 99104 KB Ok
94 Correct 480 ms 98592 KB Ok
95 Correct 422 ms 93756 KB Ok
96 Correct 602 ms 95108 KB Ok
97 Correct 523 ms 94536 KB Ok
98 Correct 399 ms 93308 KB Ok
99 Correct 465 ms 94024 KB Ok
100 Correct 495 ms 94252 KB Ok
101 Correct 502 ms 94316 KB Ok
102 Correct 474 ms 94280 KB Ok
103 Correct 532 ms 94280 KB Ok
104 Correct 582 ms 95300 KB Ok
105 Correct 553 ms 94796 KB Ok
106 Correct 462 ms 94664 KB Ok
107 Correct 490 ms 94572 KB Ok
108 Correct 604 ms 95416 KB Ok
109 Correct 703 ms 95088 KB Ok
110 Execution timed out 2064 ms 121568 KB Time limit exceeded
111 Halted 0 ms 0 KB -