oj.uz

답안 #1114151

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1114151 2024-11-18T08:54:21 Z vjudge1 Nice sequence (IZhO18_sequence) C++17
43 / 100
 2000 ms 36424 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);
        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) {
        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] = 0,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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 29264 KB Ok
2 Correct 5 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 Correct 5 ms 29356 KB Ok
7 Correct 6 ms 29264 KB Ok
8 Correct 5 ms 29264 KB Ok
9 Correct 5 ms 29264 KB Ok
10 Correct 6 ms 29264 KB Ok
11 Correct 6 ms 29264 KB Ok
12 Correct 5 ms 29264 KB Ok

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 29264 KB Ok
2 Correct 6 ms 29264 KB Ok
3 Correct 6 ms 25168 KB Ok
4 Correct 9 ms 25168 KB Ok
5 Correct 6 ms 29264 KB Ok
6 Correct 31 ms 29492 KB Ok
7 Correct 504 ms 26316 KB Ok
8 Correct 81 ms 27720 KB Ok
9 Correct 1037 ms 30436 KB Ok
10 Correct 178 ms 29944 KB Ok

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 29264 KB Ok
2 Correct 5 ms 29436 KB Ok
3 Correct 7 ms 29264 KB Ok
4 Correct 5 ms 29264 KB Ok
5 Correct 5 ms 29264 KB Ok
6 Correct 8 ms 25272 KB Ok
7 Correct 6 ms 25168 KB Ok
8 Correct 7 ms 29264 KB Ok
9 Correct 6 ms 29264 KB Ok
10 Correct 10 ms 25040 KB Ok
11 Correct 10 ms 25168 KB Ok

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 25168 KB Ok
2 Correct 8 ms 25168 KB Ok
3 Correct 8 ms 25168 KB Ok
4 Correct 6 ms 27392 KB Ok
5 Correct 6 ms 25168 KB Ok
6 Execution timed out 2068 ms 34724 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 29264 KB Ok
2 Correct 5 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 Correct 5 ms 29356 KB Ok
7 Correct 6 ms 29264 KB Ok
8 Correct 5 ms 29264 KB Ok
9 Correct 5 ms 29264 KB Ok
10 Correct 6 ms 29264 KB Ok
11 Correct 6 ms 29264 KB Ok
12 Correct 5 ms 29264 KB Ok
13 Correct 6 ms 29264 KB Ok
14 Correct 5 ms 29436 KB Ok
15 Correct 7 ms 29264 KB Ok
16 Correct 5 ms 29264 KB Ok
17 Correct 5 ms 29264 KB Ok
18 Correct 8 ms 25272 KB Ok
19 Correct 6 ms 25168 KB Ok
20 Correct 7 ms 29264 KB Ok
21 Correct 6 ms 29264 KB Ok
22 Correct 10 ms 25040 KB Ok
23 Correct 10 ms 25168 KB Ok
24 Correct 7 ms 29264 KB Ok
25 Correct 7 ms 29432 KB Ok
26 Correct 9 ms 25440 KB Ok
27 Correct 10 ms 25424 KB Ok
28 Correct 11 ms 25168 KB Ok
29 Correct 7 ms 25256 KB Ok
30 Correct 6 ms 25168 KB Ok
31 Correct 7 ms 27620 KB Ok
32 Correct 7 ms 25424 KB Ok
33 Correct 6 ms 29564 KB Ok
34 Correct 11 ms 27484 KB Ok
35 Correct 13 ms 29568 KB Ok
36 Correct 20 ms 29776 KB Ok
37 Correct 14 ms 29520 KB Ok
38 Correct 16 ms 29520 KB Ok
39 Correct 15 ms 29520 KB Ok
40 Correct 14 ms 27728 KB Ok
41 Correct 13 ms 29520 KB Ok
42 Correct 13 ms 29520 KB Ok
43 Correct 12 ms 27896 KB Ok

Subtask #6
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 29264 KB Ok
2 Correct 5 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 Correct 5 ms 29356 KB Ok
7 Correct 6 ms 29264 KB Ok
8 Correct 5 ms 29264 KB Ok
9 Correct 5 ms 29264 KB Ok
10 Correct 6 ms 29264 KB Ok
11 Correct 6 ms 29264 KB Ok
12 Correct 5 ms 29264 KB Ok
13 Correct 5 ms 29264 KB Ok
14 Correct 6 ms 29264 KB Ok
15 Correct 6 ms 25168 KB Ok
16 Correct 9 ms 25168 KB Ok
17 Correct 6 ms 29264 KB Ok
18 Correct 31 ms 29492 KB Ok
19 Correct 504 ms 26316 KB Ok
20 Correct 81 ms 27720 KB Ok
21 Correct 1037 ms 30436 KB Ok
22 Correct 178 ms 29944 KB Ok
23 Correct 6 ms 29264 KB Ok
24 Correct 5 ms 29436 KB Ok
25 Correct 7 ms 29264 KB Ok
26 Correct 5 ms 29264 KB Ok
27 Correct 5 ms 29264 KB Ok
28 Correct 8 ms 25272 KB Ok
29 Correct 6 ms 25168 KB Ok
30 Correct 7 ms 29264 KB Ok
31 Correct 6 ms 29264 KB Ok
32 Correct 10 ms 25040 KB Ok
33 Correct 10 ms 25168 KB Ok
34 Correct 7 ms 29264 KB Ok
35 Correct 7 ms 29432 KB Ok
36 Correct 9 ms 25440 KB Ok
37 Correct 10 ms 25424 KB Ok
38 Correct 11 ms 25168 KB Ok
39 Correct 7 ms 25256 KB Ok
40 Correct 6 ms 25168 KB Ok
41 Correct 7 ms 27620 KB Ok
42 Correct 7 ms 25424 KB Ok
43 Correct 6 ms 29564 KB Ok
44 Correct 11 ms 27484 KB Ok
45 Correct 13 ms 29568 KB Ok
46 Correct 20 ms 29776 KB Ok
47 Correct 14 ms 29520 KB Ok
48 Correct 16 ms 29520 KB Ok
49 Correct 15 ms 29520 KB Ok
50 Correct 14 ms 27728 KB Ok
51 Correct 13 ms 29520 KB Ok
52 Correct 13 ms 29520 KB Ok
53 Correct 12 ms 27896 KB Ok
54 Correct 56 ms 31044 KB Ok
55 Correct 73 ms 36424 KB Ok
56 Correct 65 ms 33096 KB Ok
57 Correct 47 ms 30184 KB Ok
58 Correct 79 ms 32584 KB Ok
59 Correct 69 ms 35912 KB Ok
60 Correct 51 ms 35400 KB Ok
61 Correct 51 ms 35912 KB Ok
62 Correct 85 ms 36424 KB Ok
63 Correct 63 ms 35912 KB Ok
64 Correct 78 ms 36400 KB Ok
65 Correct 73 ms 36424 KB Ok
66 Correct 55 ms 35912 KB Ok
67 Correct 63 ms 30536 KB Ok
68 Correct 90 ms 29512 KB Ok
69 Execution timed out 2081 ms 35400 KB Time limit exceeded
70 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 29264 KB Ok
2 Correct 5 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 Correct 5 ms 29356 KB Ok
7 Correct 6 ms 29264 KB Ok
8 Correct 5 ms 29264 KB Ok
9 Correct 5 ms 29264 KB Ok
10 Correct 6 ms 29264 KB Ok
11 Correct 6 ms 29264 KB Ok
12 Correct 5 ms 29264 KB Ok
13 Correct 5 ms 29264 KB Ok
14 Correct 6 ms 29264 KB Ok
15 Correct 6 ms 25168 KB Ok
16 Correct 9 ms 25168 KB Ok
17 Correct 6 ms 29264 KB Ok
18 Correct 31 ms 29492 KB Ok
19 Correct 504 ms 26316 KB Ok
20 Correct 81 ms 27720 KB Ok
21 Correct 1037 ms 30436 KB Ok
22 Correct 178 ms 29944 KB Ok
23 Correct 6 ms 29264 KB Ok
24 Correct 5 ms 29436 KB Ok
25 Correct 7 ms 29264 KB Ok
26 Correct 5 ms 29264 KB Ok
27 Correct 5 ms 29264 KB Ok
28 Correct 8 ms 25272 KB Ok
29 Correct 6 ms 25168 KB Ok
30 Correct 7 ms 29264 KB Ok
31 Correct 6 ms 29264 KB Ok
32 Correct 10 ms 25040 KB Ok
33 Correct 10 ms 25168 KB Ok
34 Correct 10 ms 25168 KB Ok
35 Correct 8 ms 25168 KB Ok
36 Correct 8 ms 25168 KB Ok
37 Correct 6 ms 27392 KB Ok
38 Correct 6 ms 25168 KB Ok
39 Execution timed out 2068 ms 34724 KB Time limit exceeded
40 Halted 0 ms 0 KB -