oj.uz

Submission #1114146

# Submission time Handle Problem Language Result Execution time Memory
1114146 2024-11-18T08:49:46 Z vjudge1 Nice sequence (IZhO18_sequence) C++17
20 / 100
 2000 ms 34392 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];
bool vis[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);
        assert(a != b);
        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) {
        cerr << node << endl;
        vis[node] = 1;
        for (auto it : edges[node]) dfs(it);
        return v[node] = mex++;
    }
    void solve() {
        for (int i = 0;i<=nd;i++) {
            if (!vis[i]) dfs(i);
        }
    }
};
void solve() { 
    int n,m;
    cin >> n >> m;
    int r = 0;
    DSU dsu;
    dad[0] = 0,sz[0] = 0,vis[0] = 0,edges[0].clear();
    for (int i = 1;i<LIM;i++) {
        dad[i] = i,sz[i] = 1,vis[i] = 0,edges[i].clear();
        cerr << i << '\n';
        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;
    for (int i = 1;i<=r;i++) {
        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 30 ms 23888 KB Ok
2 Correct 39 ms 23888 KB Ok
3 Correct 20 ms 23888 KB Ok
4 Correct 22 ms 23888 KB Ok
5 Correct 22 ms 23824 KB Ok
6 Correct 21 ms 23888 KB Ok
7 Correct 20 ms 23888 KB Ok
8 Correct 20 ms 23888 KB Ok
9 Correct 23 ms 23888 KB Ok
10 Correct 20 ms 23888 KB Ok
11 Correct 21 ms 23900 KB Ok
12 Correct 19 ms 23888 KB Ok

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23888 KB Ok
2 Correct 18 ms 23888 KB Ok
3 Correct 22 ms 23888 KB Ok
4 Correct 27 ms 23824 KB Ok
5 Correct 29 ms 23888 KB Ok
6 Execution timed out 2061 ms 26952 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23888 KB Ok
2 Correct 17 ms 23900 KB Ok
3 Correct 16 ms 23888 KB Ok
4 Correct 23 ms 23900 KB Ok
5 Correct 18 ms 23888 KB Ok
6 Correct 18 ms 23888 KB Ok
7 Correct 18 ms 23936 KB Ok
8 Correct 19 ms 23868 KB Ok
9 Correct 18 ms 23888 KB Ok
10 Correct 20 ms 23816 KB Ok
11 Correct 18 ms 23888 KB Ok

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23900 KB Ok
2 Correct 20 ms 23888 KB Ok
3 Correct 20 ms 23888 KB Ok
4 Correct 24 ms 23888 KB Ok
5 Correct 29 ms 23888 KB Ok
6 Execution timed out 2078 ms 34392 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 23888 KB Ok
2 Correct 39 ms 23888 KB Ok
3 Correct 20 ms 23888 KB Ok
4 Correct 22 ms 23888 KB Ok
5 Correct 22 ms 23824 KB Ok
6 Correct 21 ms 23888 KB Ok
7 Correct 20 ms 23888 KB Ok
8 Correct 20 ms 23888 KB Ok
9 Correct 23 ms 23888 KB Ok
10 Correct 20 ms 23888 KB Ok
11 Correct 21 ms 23900 KB Ok
12 Correct 19 ms 23888 KB Ok
13 Correct 17 ms 23888 KB Ok
14 Correct 17 ms 23900 KB Ok
15 Correct 16 ms 23888 KB Ok
16 Correct 23 ms 23900 KB Ok
17 Correct 18 ms 23888 KB Ok
18 Correct 18 ms 23888 KB Ok
19 Correct 18 ms 23936 KB Ok
20 Correct 19 ms 23868 KB Ok
21 Correct 18 ms 23888 KB Ok
22 Correct 20 ms 23816 KB Ok
23 Correct 18 ms 23888 KB Ok
24 Correct 184 ms 24136 KB Ok
25 Correct 201 ms 24404 KB Ok
26 Correct 201 ms 24392 KB Ok
27 Correct 191 ms 24392 KB Ok
28 Correct 152 ms 24260 KB Ok
29 Correct 137 ms 24136 KB Ok
30 Correct 177 ms 24256 KB Ok
31 Correct 181 ms 24392 KB Ok
32 Correct 184 ms 24332 KB Ok
33 Correct 219 ms 24304 KB Ok
34 Correct 1182 ms 26320 KB Ok
35 Correct 1512 ms 26868 KB Ok
36 Execution timed out 2070 ms 27836 KB Time limit exceeded
37 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 23888 KB Ok
2 Correct 39 ms 23888 KB Ok
3 Correct 20 ms 23888 KB Ok
4 Correct 22 ms 23888 KB Ok
5 Correct 22 ms 23824 KB Ok
6 Correct 21 ms 23888 KB Ok
7 Correct 20 ms 23888 KB Ok
8 Correct 20 ms 23888 KB Ok
9 Correct 23 ms 23888 KB Ok
10 Correct 20 ms 23888 KB Ok
11 Correct 21 ms 23900 KB Ok
12 Correct 19 ms 23888 KB Ok
13 Correct 18 ms 23888 KB Ok
14 Correct 18 ms 23888 KB Ok
15 Correct 22 ms 23888 KB Ok
16 Correct 27 ms 23824 KB Ok
17 Correct 29 ms 23888 KB Ok
18 Execution timed out 2061 ms 26952 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 23888 KB Ok
2 Correct 39 ms 23888 KB Ok
3 Correct 20 ms 23888 KB Ok
4 Correct 22 ms 23888 KB Ok
5 Correct 22 ms 23824 KB Ok
6 Correct 21 ms 23888 KB Ok
7 Correct 20 ms 23888 KB Ok
8 Correct 20 ms 23888 KB Ok
9 Correct 23 ms 23888 KB Ok
10 Correct 20 ms 23888 KB Ok
11 Correct 21 ms 23900 KB Ok
12 Correct 19 ms 23888 KB Ok
13 Correct 18 ms 23888 KB Ok
14 Correct 18 ms 23888 KB Ok
15 Correct 22 ms 23888 KB Ok
16 Correct 27 ms 23824 KB Ok
17 Correct 29 ms 23888 KB Ok
18 Execution timed out 2061 ms 26952 KB Time limit exceeded
19 Halted 0 ms 0 KB -