oj.uz

Submission #1114128

# Submission time Handle Problem Language Result Execution time Memory
1114128 2024-11-18T08:20:28 Z vjudge1 Nice sequence (IZhO18_sequence) C++17
61 / 100
 457 ms 46420 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 = 500001;
vi edges[LIM];
bool vis[LIM],act[LIM];
int v[LIM];
struct DAG {
    int nd;
    bool cyclic = 0;
    inline void reset() {
        cyclic = 0;;
        for (int i = 0;i<=nd;i++) edges[i].clear(),vis[i] = 0,act[i] = 0;
    }
    void cyclecheck(int node) {
        if (vis[node]) return;
        if (cyclic) return;
        vis[node] = act[node] = 1;
        for (auto it : edges[node]) {
            if (act[it]) {
                cyclic = 1;
                return;
            }
            else if (!vis[it]) cyclecheck(it);
        }
        act[node] = 0;
    }
    void checkcycle() {
        for (int i = 0;i<=nd;i++) {
            cyclecheck(i);
            if (cyclic) break;
        }
    }
    int mex = 1;
    int dfs(int node) {
        if (vis[node]) return v[node];
        vis[node] = 1;
        for (auto it : edges[node]) dfs(it);
        return v[node] = mex++;
    }
    void solve() {
        for (int i = 0;i<=nd;i++) vis[i] = 0;
        for (int i = 0;i<=nd;i++) dfs(i);
    }
};
void solve() { 
    int n,m;
    cin >> n >> m;
    int l = 1;
    int r = LIM-1; // tune
    DAG D;
    while (l<=r) {
        int k = (l+r) >> 1;
        D.nd = k;
        for (int i = 1;i<=k;i++) {
            if (i >= m) edges[i].push_back(i-m);
            if (i >= n) edges[i-n].push_back(i);
        }
        D.checkcycle();
        if (!D.cyclic) l = k+1;
        else r = k-1;
        D.reset();
    }
    memset(v,-1,sizeof v);
    cout << r << '\n';
    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 37 ms 22864 KB Ok
2 Correct 39 ms 22864 KB Ok
3 Correct 39 ms 22864 KB Ok
4 Correct 36 ms 22812 KB Ok
5 Correct 38 ms 22944 KB Ok
6 Correct 41 ms 22772 KB Ok
7 Correct 41 ms 22864 KB Ok
8 Correct 37 ms 22864 KB Ok
9 Correct 37 ms 22772 KB Ok
10 Correct 38 ms 22864 KB Ok
11 Correct 39 ms 22832 KB Ok
12 Correct 38 ms 22832 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 22864 KB Ok
2 Correct 48 ms 22864 KB Ok
3 Correct 40 ms 22864 KB Ok
4 Correct 40 ms 22864 KB Ok
5 Correct 44 ms 22940 KB Ok
6 Correct 44 ms 22876 KB Ok
7 Correct 57 ms 23480 KB Ok
8 Correct 49 ms 23120 KB Ok
9 Correct 59 ms 23672 KB Ok
10 Correct 51 ms 23368 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 22864 KB Ok
2 Correct 41 ms 22952 KB Ok
3 Correct 40 ms 22864 KB Ok
4 Correct 40 ms 22864 KB Ok
5 Correct 39 ms 22856 KB Ok
6 Correct 37 ms 22864 KB Ok
7 Correct 47 ms 22876 KB Ok
8 Correct 42 ms 22864 KB Ok
9 Correct 41 ms 22908 KB Ok
10 Correct 36 ms 23032 KB Ok
11 Correct 38 ms 22864 KB Ok

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 22856 KB Ok
2 Correct 39 ms 23040 KB Ok
3 Correct 41 ms 22856 KB Ok
4 Correct 42 ms 22868 KB Ok
5 Correct 39 ms 22932 KB Ok
6 Incorrect 457 ms 46420 KB there is incorrect sequence
7 Halted 0 ms 0 KB -

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 22864 KB Ok
2 Correct 39 ms 22864 KB Ok
3 Correct 39 ms 22864 KB Ok
4 Correct 36 ms 22812 KB Ok
5 Correct 38 ms 22944 KB Ok
6 Correct 41 ms 22772 KB Ok
7 Correct 41 ms 22864 KB Ok
8 Correct 37 ms 22864 KB Ok
9 Correct 37 ms 22772 KB Ok
10 Correct 38 ms 22864 KB Ok
11 Correct 39 ms 22832 KB Ok
12 Correct 38 ms 22832 KB Ok
13 Correct 29 ms 22864 KB Ok
14 Correct 41 ms 22952 KB Ok
15 Correct 40 ms 22864 KB Ok
16 Correct 40 ms 22864 KB Ok
17 Correct 39 ms 22856 KB Ok
18 Correct 37 ms 22864 KB Ok
19 Correct 47 ms 22876 KB Ok
20 Correct 42 ms 22864 KB Ok
21 Correct 41 ms 22908 KB Ok
22 Correct 36 ms 23032 KB Ok
23 Correct 38 ms 22864 KB Ok
24 Correct 42 ms 22764 KB Ok
25 Correct 45 ms 22964 KB Ok
26 Correct 43 ms 23048 KB Ok
27 Correct 44 ms 22776 KB Ok
28 Correct 40 ms 22936 KB Ok
29 Correct 44 ms 22960 KB Ok
30 Correct 38 ms 22964 KB Ok
31 Correct 44 ms 22864 KB Ok
32 Correct 44 ms 22888 KB Ok
33 Correct 40 ms 22864 KB Ok
34 Correct 44 ms 23156 KB Ok
35 Correct 45 ms 23112 KB Ok
36 Correct 44 ms 23064 KB Ok
37 Correct 47 ms 23132 KB Ok
38 Correct 46 ms 23096 KB Ok
39 Correct 45 ms 23124 KB Ok
40 Correct 46 ms 23116 KB Ok
41 Correct 68 ms 23164 KB Ok
42 Correct 44 ms 23120 KB Ok
43 Correct 46 ms 23112 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 22864 KB Ok
2 Correct 39 ms 22864 KB Ok
3 Correct 39 ms 22864 KB Ok
4 Correct 36 ms 22812 KB Ok
5 Correct 38 ms 22944 KB Ok
6 Correct 41 ms 22772 KB Ok
7 Correct 41 ms 22864 KB Ok
8 Correct 37 ms 22864 KB Ok
9 Correct 37 ms 22772 KB Ok
10 Correct 38 ms 22864 KB Ok
11 Correct 39 ms 22832 KB Ok
12 Correct 38 ms 22832 KB Ok
13 Correct 42 ms 22864 KB Ok
14 Correct 48 ms 22864 KB Ok
15 Correct 40 ms 22864 KB Ok
16 Correct 40 ms 22864 KB Ok
17 Correct 44 ms 22940 KB Ok
18 Correct 44 ms 22876 KB Ok
19 Correct 57 ms 23480 KB Ok
20 Correct 49 ms 23120 KB Ok
21 Correct 59 ms 23672 KB Ok
22 Correct 51 ms 23368 KB Ok
23 Correct 29 ms 22864 KB Ok
24 Correct 41 ms 22952 KB Ok
25 Correct 40 ms 22864 KB Ok
26 Correct 40 ms 22864 KB Ok
27 Correct 39 ms 22856 KB Ok
28 Correct 37 ms 22864 KB Ok
29 Correct 47 ms 22876 KB Ok
30 Correct 42 ms 22864 KB Ok
31 Correct 41 ms 22908 KB Ok
32 Correct 36 ms 23032 KB Ok
33 Correct 38 ms 22864 KB Ok
34 Correct 42 ms 22764 KB Ok
35 Correct 45 ms 22964 KB Ok
36 Correct 43 ms 23048 KB Ok
37 Correct 44 ms 22776 KB Ok
38 Correct 40 ms 22936 KB Ok
39 Correct 44 ms 22960 KB Ok
40 Correct 38 ms 22964 KB Ok
41 Correct 44 ms 22864 KB Ok
42 Correct 44 ms 22888 KB Ok
43 Correct 40 ms 22864 KB Ok
44 Correct 44 ms 23156 KB Ok
45 Correct 45 ms 23112 KB Ok
46 Correct 44 ms 23064 KB Ok
47 Correct 47 ms 23132 KB Ok
48 Correct 46 ms 23096 KB Ok
49 Correct 45 ms 23124 KB Ok
50 Correct 46 ms 23116 KB Ok
51 Correct 68 ms 23164 KB Ok
52 Correct 44 ms 23120 KB Ok
53 Correct 46 ms 23112 KB Ok
54 Correct 119 ms 24580 KB Ok
55 Correct 152 ms 24904 KB Ok
56 Correct 139 ms 24904 KB Ok
57 Correct 100 ms 24052 KB Ok
58 Correct 121 ms 24396 KB Ok
59 Correct 115 ms 24316 KB Ok
60 Correct 109 ms 24136 KB Ok
61 Correct 107 ms 24176 KB Ok
62 Correct 132 ms 24644 KB Ok
63 Correct 113 ms 24392 KB Ok
64 Correct 146 ms 24904 KB Ok
65 Correct 123 ms 24380 KB Ok
66 Correct 119 ms 24392 KB Ok
67 Correct 110 ms 24364 KB Ok
68 Correct 143 ms 24392 KB Ok
69 Correct 319 ms 32336 KB Ok
70 Correct 376 ms 32912 KB Ok
71 Correct 291 ms 32364 KB Ok
72 Correct 356 ms 32328 KB Ok
73 Correct 314 ms 32332 KB Ok
74 Correct 343 ms 32140 KB Ok
75 Correct 321 ms 31816 KB Ok
76 Correct 371 ms 32588 KB Ok
77 Correct 287 ms 31816 KB Ok
78 Correct 362 ms 32380 KB Ok
79 Correct 323 ms 32584 KB Ok
80 Correct 333 ms 32584 KB Ok
81 Correct 335 ms 32584 KB Ok
82 Correct 312 ms 32328 KB Ok
83 Correct 281 ms 31816 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 22864 KB Ok
2 Correct 39 ms 22864 KB Ok
3 Correct 39 ms 22864 KB Ok
4 Correct 36 ms 22812 KB Ok
5 Correct 38 ms 22944 KB Ok
6 Correct 41 ms 22772 KB Ok
7 Correct 41 ms 22864 KB Ok
8 Correct 37 ms 22864 KB Ok
9 Correct 37 ms 22772 KB Ok
10 Correct 38 ms 22864 KB Ok
11 Correct 39 ms 22832 KB Ok
12 Correct 38 ms 22832 KB Ok
13 Correct 42 ms 22864 KB Ok
14 Correct 48 ms 22864 KB Ok
15 Correct 40 ms 22864 KB Ok
16 Correct 40 ms 22864 KB Ok
17 Correct 44 ms 22940 KB Ok
18 Correct 44 ms 22876 KB Ok
19 Correct 57 ms 23480 KB Ok
20 Correct 49 ms 23120 KB Ok
21 Correct 59 ms 23672 KB Ok
22 Correct 51 ms 23368 KB Ok
23 Correct 29 ms 22864 KB Ok
24 Correct 41 ms 22952 KB Ok
25 Correct 40 ms 22864 KB Ok
26 Correct 40 ms 22864 KB Ok
27 Correct 39 ms 22856 KB Ok
28 Correct 37 ms 22864 KB Ok
29 Correct 47 ms 22876 KB Ok
30 Correct 42 ms 22864 KB Ok
31 Correct 41 ms 22908 KB Ok
32 Correct 36 ms 23032 KB Ok
33 Correct 38 ms 22864 KB Ok
34 Correct 41 ms 22856 KB Ok
35 Correct 39 ms 23040 KB Ok
36 Correct 41 ms 22856 KB Ok
37 Correct 42 ms 22868 KB Ok
38 Correct 39 ms 22932 KB Ok
39 Incorrect 457 ms 46420 KB there is incorrect sequence
40 Halted 0 ms 0 KB -