oj.uz

Submission #1114143

# Submission time Handle Problem Language Result Execution time Memory
1114143 2024-11-18T08:47:09 Z vjudge1 Nice sequence (IZhO18_sequence) C++17
20 / 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];
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() { 
    for (int i = 0;i<LIM;i++) {
        dad[i] = i,sz[i] =1,vis[i] = 0;
        edges[i].clear();
    }
    int n,m;
    cin >> n >> m;
    int r = 0;
    DSU dsu;
    for (int i = 1;i<LIM;i++) {
        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 54 ms 32592 KB Ok
2 Correct 65 ms 32760 KB Ok
3 Correct 43 ms 32592 KB Ok
4 Correct 45 ms 32592 KB Ok
5 Correct 44 ms 32592 KB Ok
6 Correct 49 ms 32592 KB Ok
7 Correct 44 ms 32588 KB Ok
8 Correct 42 ms 32592 KB Ok
9 Correct 44 ms 32592 KB Ok
10 Correct 43 ms 32688 KB Ok
11 Correct 43 ms 32592 KB Ok
12 Correct 44 ms 32592 KB Ok

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 32592 KB Ok
2 Correct 41 ms 32592 KB Ok
3 Correct 45 ms 32592 KB Ok
4 Correct 49 ms 32592 KB Ok
5 Correct 52 ms 32592 KB Ok
6 Execution timed out 2063 ms 35696 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 32592 KB Ok
2 Correct 37 ms 32580 KB Ok
3 Correct 39 ms 32620 KB Ok
4 Correct 40 ms 32536 KB Ok
5 Correct 41 ms 32592 KB Ok
6 Correct 40 ms 32696 KB Ok
7 Correct 41 ms 32592 KB Ok
8 Correct 41 ms 32624 KB Ok
9 Correct 41 ms 32592 KB Ok
10 Correct 44 ms 32584 KB Ok
11 Correct 41 ms 32592 KB Ok

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 32592 KB Ok
2 Correct 42 ms 32592 KB Ok
3 Correct 45 ms 32592 KB Ok
4 Correct 50 ms 32584 KB Ok
5 Correct 51 ms 32584 KB Ok
6 Execution timed out 2074 ms 41624 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 32592 KB Ok
2 Correct 65 ms 32760 KB Ok
3 Correct 43 ms 32592 KB Ok
4 Correct 45 ms 32592 KB Ok
5 Correct 44 ms 32592 KB Ok
6 Correct 49 ms 32592 KB Ok
7 Correct 44 ms 32588 KB Ok
8 Correct 42 ms 32592 KB Ok
9 Correct 44 ms 32592 KB Ok
10 Correct 43 ms 32688 KB Ok
11 Correct 43 ms 32592 KB Ok
12 Correct 44 ms 32592 KB Ok
13 Correct 30 ms 32592 KB Ok
14 Correct 37 ms 32580 KB Ok
15 Correct 39 ms 32620 KB Ok
16 Correct 40 ms 32536 KB Ok
17 Correct 41 ms 32592 KB Ok
18 Correct 40 ms 32696 KB Ok
19 Correct 41 ms 32592 KB Ok
20 Correct 41 ms 32624 KB Ok
21 Correct 41 ms 32592 KB Ok
22 Correct 44 ms 32584 KB Ok
23 Correct 41 ms 32592 KB Ok
24 Correct 223 ms 33072 KB Ok
25 Correct 230 ms 33104 KB Ok
26 Correct 232 ms 33100 KB Ok
27 Correct 219 ms 33096 KB Ok
28 Correct 178 ms 32840 KB Ok
29 Correct 155 ms 32840 KB Ok
30 Correct 199 ms 33036 KB Ok
31 Correct 196 ms 33096 KB Ok
32 Correct 198 ms 32996 KB Ok
33 Correct 235 ms 33164 KB Ok
34 Correct 1168 ms 35044 KB Ok
35 Correct 1606 ms 35656 KB Ok
36 Execution timed out 2073 ms 36480 KB Time limit exceeded
37 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 32592 KB Ok
2 Correct 65 ms 32760 KB Ok
3 Correct 43 ms 32592 KB Ok
4 Correct 45 ms 32592 KB Ok
5 Correct 44 ms 32592 KB Ok
6 Correct 49 ms 32592 KB Ok
7 Correct 44 ms 32588 KB Ok
8 Correct 42 ms 32592 KB Ok
9 Correct 44 ms 32592 KB Ok
10 Correct 43 ms 32688 KB Ok
11 Correct 43 ms 32592 KB Ok
12 Correct 44 ms 32592 KB Ok
13 Correct 40 ms 32592 KB Ok
14 Correct 41 ms 32592 KB Ok
15 Correct 45 ms 32592 KB Ok
16 Correct 49 ms 32592 KB Ok
17 Correct 52 ms 32592 KB Ok
18 Execution timed out 2063 ms 35696 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 32592 KB Ok
2 Correct 65 ms 32760 KB Ok
3 Correct 43 ms 32592 KB Ok
4 Correct 45 ms 32592 KB Ok
5 Correct 44 ms 32592 KB Ok
6 Correct 49 ms 32592 KB Ok
7 Correct 44 ms 32588 KB Ok
8 Correct 42 ms 32592 KB Ok
9 Correct 44 ms 32592 KB Ok
10 Correct 43 ms 32688 KB Ok
11 Correct 43 ms 32592 KB Ok
12 Correct 44 ms 32592 KB Ok
13 Correct 40 ms 32592 KB Ok
14 Correct 41 ms 32592 KB Ok
15 Correct 45 ms 32592 KB Ok
16 Correct 49 ms 32592 KB Ok
17 Correct 52 ms 32592 KB Ok
18 Execution timed out 2063 ms 35696 KB Time limit exceeded
19 Halted 0 ms 0 KB -