oj.uz

Submission #1114158

# Submission time Handle Problem Language Result Execution time Memory
1114158 2024-11-18T08:58:10 Z vjudge1 Nice sequence (IZhO18_sequence) C++17
43 / 100
 2000 ms 41624 KB 
//Dost SEFEROĞLU
#include <bits/stdc++.h>
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#pragma GCC optimize("O3,unroll-loops")
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 = 1e6+1;
vi edges[LIM];
int v[LIM];
int dad[LIM],sz[LIM];
struct DSU {
    int find(int x) {
        if (x == dad[x]) return x;
        return dad[x] = find(dad[x]);
    }
    void unite(int x,int y) {
        int a = find(x),b = find(y);
        if (sz[a] > sz[b]) swap(a,b);
        dad[a] = b;
        sz[b]+=sz[a];
    }
};
struct DAG {
    int nd;
    int mex = 1;
    int dfs(int node) {
        for (auto it : edges[node]) dfs(it);
        return v[node] = mex++;
    }
    void solve() {
        for (int i = 0;i<=nd;i++) if (!v[i]) dfs(i);
    }
};
void solve() { 
    int n,m;
    cin >> n >> m;
    int r = 0;
    DSU dsu;
    dad[0] = 0,sz[0] = 1,edges[0].clear();
    for (int i = 1;i<LIM;i++) {
        dad[i] = i,sz[i] = 1,edges[i].clear();
        if (i >= m) {
            if (dsu.find(i) == dsu.find(i-m)) break;
            dsu.unite(i,i-m);
        }
        if (i >= n) {
            if (dsu.find(i-n) == dsu.find(i)) break;
            dsu.unite(i,i-n);
        }
        r = i;
    }
    DAG D;
    cout << r << endl;
    D.nd = r;
    v[0] = 0;
    for (int i = 1;i<=r;i++) {
        v[i] = 0;
        if (i >= m) {
            edges[i].push_back(i-m);
        }
        if (i >= n) {
            edges[i-n].push_back(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:13:29: warning: overflow in conversion from 'double' to 'int' changes value from '2.0e+18' to '2147483647' [-Woverflow]
   13 | const int MOD = 1e9+7,inf = 2e18;
      |                             ^~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29264 KB Ok
2 Correct 5 ms 29264 KB Ok
3 Correct 5 ms 29264 KB Ok
4 Correct 5 ms 29264 KB Ok
5 Correct 5 ms 29264 KB Ok
6 Correct 30 ms 27472 KB Ok
7 Correct 516 ms 28232 KB Ok
8 Correct 92 ms 29768 KB Ok
9 Correct 1090 ms 30464 KB Ok
10 Correct 181 ms 29768 KB Ok

Subtask #3
14.0 / 14.0

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

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29432 KB Ok
2 Correct 6 ms 29264 KB Ok
3 Correct 6 ms 29264 KB Ok
4 Correct 5 ms 29264 KB Ok
5 Correct 5 ms 29264 KB Ok
6 Execution timed out 2059 ms 41624 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 29264 KB Ok
2 Correct 5 ms 29264 KB Ok
3 Correct 5 ms 29264 KB Ok
4 Correct 5 ms 29264 KB Ok
5 Correct 5 ms 29264 KB Ok
6 Correct 5 ms 29264 KB Ok
7 Correct 6 ms 29264 KB Ok
8 Correct 5 ms 29264 KB Ok
9 Correct 5 ms 29116 KB Ok
10 Correct 5 ms 29264 KB Ok
11 Correct 5 ms 29276 KB Ok
12 Correct 7 ms 29264 KB Ok
13 Correct 5 ms 29264 KB Ok
14 Correct 5 ms 29264 KB Ok
15 Correct 5 ms 29264 KB Ok
16 Correct 5 ms 29264 KB Ok
17 Correct 6 ms 29264 KB Ok
18 Correct 5 ms 29120 KB Ok
19 Correct 5 ms 29264 KB Ok
20 Correct 5 ms 29264 KB Ok
21 Correct 5 ms 29264 KB Ok
22 Correct 5 ms 29264 KB Ok
23 Correct 5 ms 27216 KB Ok
24 Correct 7 ms 29276 KB Ok
25 Correct 7 ms 29264 KB Ok
26 Correct 7 ms 29436 KB Ok
27 Correct 7 ms 29264 KB Ok
28 Correct 6 ms 29264 KB Ok
29 Correct 7 ms 29264 KB Ok
30 Correct 6 ms 29276 KB Ok
31 Correct 7 ms 29264 KB Ok
32 Correct 6 ms 27216 KB Ok
33 Correct 8 ms 29264 KB Ok
34 Correct 11 ms 29520 KB Ok
35 Correct 13 ms 29520 KB Ok
36 Correct 21 ms 29744 KB Ok
37 Correct 13 ms 29520 KB Ok
38 Correct 12 ms 29520 KB Ok
39 Correct 14 ms 25756 KB Ok
40 Correct 15 ms 25680 KB Ok
41 Correct 15 ms 25680 KB Ok
42 Correct 15 ms 25680 KB Ok
43 Correct 11 ms 27688 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 29264 KB Ok
2 Correct 5 ms 29264 KB Ok
3 Correct 5 ms 29264 KB Ok
4 Correct 5 ms 29264 KB Ok
5 Correct 5 ms 29264 KB Ok
6 Correct 5 ms 29264 KB Ok
7 Correct 6 ms 29264 KB Ok
8 Correct 5 ms 29264 KB Ok
9 Correct 5 ms 29116 KB Ok
10 Correct 5 ms 29264 KB Ok
11 Correct 5 ms 29276 KB Ok
12 Correct 7 ms 29264 KB Ok
13 Correct 5 ms 29264 KB Ok
14 Correct 5 ms 29264 KB Ok
15 Correct 5 ms 29264 KB Ok
16 Correct 5 ms 29264 KB Ok
17 Correct 5 ms 29264 KB Ok
18 Correct 30 ms 27472 KB Ok
19 Correct 516 ms 28232 KB Ok
20 Correct 92 ms 29768 KB Ok
21 Correct 1090 ms 30464 KB Ok
22 Correct 181 ms 29768 KB Ok
23 Correct 5 ms 29264 KB Ok
24 Correct 5 ms 29264 KB Ok
25 Correct 5 ms 29264 KB Ok
26 Correct 5 ms 29264 KB Ok
27 Correct 6 ms 29264 KB Ok
28 Correct 5 ms 29120 KB Ok
29 Correct 5 ms 29264 KB Ok
30 Correct 5 ms 29264 KB Ok
31 Correct 5 ms 29264 KB Ok
32 Correct 5 ms 29264 KB Ok
33 Correct 5 ms 27216 KB Ok
34 Correct 7 ms 29276 KB Ok
35 Correct 7 ms 29264 KB Ok
36 Correct 7 ms 29436 KB Ok
37 Correct 7 ms 29264 KB Ok
38 Correct 6 ms 29264 KB Ok
39 Correct 7 ms 29264 KB Ok
40 Correct 6 ms 29276 KB Ok
41 Correct 7 ms 29264 KB Ok
42 Correct 6 ms 27216 KB Ok
43 Correct 8 ms 29264 KB Ok
44 Correct 11 ms 29520 KB Ok
45 Correct 13 ms 29520 KB Ok
46 Correct 21 ms 29744 KB Ok
47 Correct 13 ms 29520 KB Ok
48 Correct 12 ms 29520 KB Ok
49 Correct 14 ms 25756 KB Ok
50 Correct 15 ms 25680 KB Ok
51 Correct 15 ms 25680 KB Ok
52 Correct 15 ms 25680 KB Ok
53 Correct 11 ms 27688 KB Ok
54 Correct 58 ms 32720 KB Ok
55 Correct 66 ms 36424 KB Ok
56 Correct 68 ms 33096 KB Ok
57 Correct 46 ms 35576 KB Ok
58 Correct 76 ms 32556 KB Ok
59 Correct 64 ms 32328 KB Ok
60 Correct 51 ms 30028 KB Ok
61 Correct 48 ms 30536 KB Ok
62 Correct 83 ms 31304 KB Ok
63 Correct 71 ms 34120 KB Ok
64 Correct 76 ms 36484 KB Ok
65 Correct 65 ms 36424 KB Ok
66 Correct 50 ms 35912 KB Ok
67 Correct 45 ms 35656 KB Ok
68 Correct 68 ms 34376 KB Ok
69 Execution timed out 2078 ms 41284 KB Time limit exceeded
70 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 29264 KB Ok
2 Correct 5 ms 29264 KB Ok
3 Correct 5 ms 29264 KB Ok
4 Correct 5 ms 29264 KB Ok
5 Correct 5 ms 29264 KB Ok
6 Correct 5 ms 29264 KB Ok
7 Correct 6 ms 29264 KB Ok
8 Correct 5 ms 29264 KB Ok
9 Correct 5 ms 29116 KB Ok
10 Correct 5 ms 29264 KB Ok
11 Correct 5 ms 29276 KB Ok
12 Correct 7 ms 29264 KB Ok
13 Correct 5 ms 29264 KB Ok
14 Correct 5 ms 29264 KB Ok
15 Correct 5 ms 29264 KB Ok
16 Correct 5 ms 29264 KB Ok
17 Correct 5 ms 29264 KB Ok
18 Correct 30 ms 27472 KB Ok
19 Correct 516 ms 28232 KB Ok
20 Correct 92 ms 29768 KB Ok
21 Correct 1090 ms 30464 KB Ok
22 Correct 181 ms 29768 KB Ok
23 Correct 5 ms 29264 KB Ok
24 Correct 5 ms 29264 KB Ok
25 Correct 5 ms 29264 KB Ok
26 Correct 5 ms 29264 KB Ok
27 Correct 6 ms 29264 KB Ok
28 Correct 5 ms 29120 KB Ok
29 Correct 5 ms 29264 KB Ok
30 Correct 5 ms 29264 KB Ok
31 Correct 5 ms 29264 KB Ok
32 Correct 5 ms 29264 KB Ok
33 Correct 5 ms 27216 KB Ok
34 Correct 5 ms 29432 KB Ok
35 Correct 6 ms 29264 KB Ok
36 Correct 6 ms 29264 KB Ok
37 Correct 5 ms 29264 KB Ok
38 Correct 5 ms 29264 KB Ok
39 Execution timed out 2059 ms 41624 KB Time limit exceeded
40 Halted 0 ms 0 KB -