oj.uz

Submission #1114145

# Submission time Handle Problem Language Result Execution time Memory
1114145 2024-11-18T08:48:57 Z vjudge1 Nice sequence (IZhO18_sequence) C++17
20 / 100
 2000 ms 34572 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);
        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 31 ms 23888 KB Ok
2 Correct 40 ms 23888 KB Ok
3 Correct 20 ms 23888 KB Ok
4 Correct 24 ms 23888 KB Ok
5 Correct 25 ms 23920 KB Ok
6 Correct 21 ms 23976 KB Ok
7 Correct 21 ms 23976 KB Ok
8 Correct 20 ms 23888 KB Ok
9 Correct 22 ms 23900 KB Ok
10 Correct 20 ms 23888 KB Ok
11 Correct 21 ms 23888 KB Ok
12 Correct 20 ms 23888 KB Ok

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23772 KB Ok
2 Correct 20 ms 23888 KB Ok
3 Correct 23 ms 23888 KB Ok
4 Correct 26 ms 23888 KB Ok
5 Correct 30 ms 23888 KB Ok
6 Execution timed out 2060 ms 26944 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

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

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23888 KB Ok
2 Correct 25 ms 23848 KB Ok
3 Correct 21 ms 23888 KB Ok
4 Correct 24 ms 23888 KB Ok
5 Correct 30 ms 23976 KB Ok
6 Execution timed out 2054 ms 34572 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 23888 KB Ok
2 Correct 40 ms 23888 KB Ok
3 Correct 20 ms 23888 KB Ok
4 Correct 24 ms 23888 KB Ok
5 Correct 25 ms 23920 KB Ok
6 Correct 21 ms 23976 KB Ok
7 Correct 21 ms 23976 KB Ok
8 Correct 20 ms 23888 KB Ok
9 Correct 22 ms 23900 KB Ok
10 Correct 20 ms 23888 KB Ok
11 Correct 21 ms 23888 KB Ok
12 Correct 20 ms 23888 KB Ok
13 Correct 15 ms 23888 KB Ok
14 Correct 16 ms 23888 KB Ok
15 Correct 18 ms 23888 KB Ok
16 Correct 23 ms 23888 KB Ok
17 Correct 19 ms 23888 KB Ok
18 Correct 17 ms 23888 KB Ok
19 Correct 19 ms 23900 KB Ok
20 Correct 17 ms 23888 KB Ok
21 Correct 17 ms 23888 KB Ok
22 Correct 17 ms 23888 KB Ok
23 Correct 18 ms 23888 KB Ok
24 Correct 181 ms 24276 KB Ok
25 Correct 200 ms 24392 KB Ok
26 Correct 196 ms 24392 KB Ok
27 Correct 194 ms 24392 KB Ok
28 Correct 146 ms 24136 KB Ok
29 Correct 131 ms 24092 KB Ok
30 Correct 187 ms 24264 KB Ok
31 Correct 170 ms 24384 KB Ok
32 Correct 176 ms 24360 KB Ok
33 Correct 210 ms 24392 KB Ok
34 Correct 1155 ms 26296 KB Ok
35 Correct 1543 ms 26940 KB Ok
36 Execution timed out 2054 ms 27864 KB Time limit exceeded
37 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 23888 KB Ok
2 Correct 40 ms 23888 KB Ok
3 Correct 20 ms 23888 KB Ok
4 Correct 24 ms 23888 KB Ok
5 Correct 25 ms 23920 KB Ok
6 Correct 21 ms 23976 KB Ok
7 Correct 21 ms 23976 KB Ok
8 Correct 20 ms 23888 KB Ok
9 Correct 22 ms 23900 KB Ok
10 Correct 20 ms 23888 KB Ok
11 Correct 21 ms 23888 KB Ok
12 Correct 20 ms 23888 KB Ok
13 Correct 18 ms 23772 KB Ok
14 Correct 20 ms 23888 KB Ok
15 Correct 23 ms 23888 KB Ok
16 Correct 26 ms 23888 KB Ok
17 Correct 30 ms 23888 KB Ok
18 Execution timed out 2060 ms 26944 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 23888 KB Ok
2 Correct 40 ms 23888 KB Ok
3 Correct 20 ms 23888 KB Ok
4 Correct 24 ms 23888 KB Ok
5 Correct 25 ms 23920 KB Ok
6 Correct 21 ms 23976 KB Ok
7 Correct 21 ms 23976 KB Ok
8 Correct 20 ms 23888 KB Ok
9 Correct 22 ms 23900 KB Ok
10 Correct 20 ms 23888 KB Ok
11 Correct 21 ms 23888 KB Ok
12 Correct 20 ms 23888 KB Ok
13 Correct 18 ms 23772 KB Ok
14 Correct 20 ms 23888 KB Ok
15 Correct 23 ms 23888 KB Ok
16 Correct 26 ms 23888 KB Ok
17 Correct 30 ms 23888 KB Ok
18 Execution timed out 2060 ms 26944 KB Time limit exceeded
19 Halted 0 ms 0 KB -