oj.uz

Submission #1114119

# Submission time Handle Problem Language Result Execution time Memory
1114119 2024-11-18T08:11:33 Z vjudge1 Nice sequence (IZhO18_sequence) C++17
21 / 100
 796 ms 262144 KB 
//Dost SEFEROĞLU
#include <bits/stdc++.h>
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
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 = 5000001;
vi edges[LIM];
bool vis[LIM],act[LIM];
int v[LIM];
struct DAG {
    int nd;
    bool cyclic = 0;
    void addedge(int a,int b) {
        edges[a].push_back(b);
    }
    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;
        if (edges[node].empty()) return v[node] = mex++;
        int mx = 0;
        for (auto it : edges[node]) {
            mx = max(mx,dfs(it));
        }
        return v[node] = mx+1;
    }
    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) D.addedge(i,i-m);
            if (i >= n) D.addedge(i-n,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) D.addedge(i,i-m);
        if (i >= n) D.addedge(i-n,i);
    } 
    D.solve();
    for (int i = 1;i<=r;i++) {
        assert(v[i] != v[i-1]);
        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:12:29: warning: overflow in conversion from 'double' to 'int' changes value from '2.0e+18' to '2147483647' [-Woverflow]
   12 | const int MOD = 1e9+7,inf = 2e18;
      |                             ^~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 221256 KB Ok
2 Correct 458 ms 221000 KB Ok
3 Correct 455 ms 221000 KB Ok
4 Correct 433 ms 221072 KB Ok
5 Correct 433 ms 221256 KB Ok
6 Correct 450 ms 221000 KB Ok
7 Correct 454 ms 221000 KB Ok
8 Correct 451 ms 221000 KB Ok
9 Correct 429 ms 221000 KB Ok
10 Correct 455 ms 223560 KB Ok
11 Correct 445 ms 221072 KB Ok
12 Correct 459 ms 221000 KB Ok

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 585 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 221056 KB Ok
2 Correct 497 ms 221008 KB Ok
3 Runtime error 544 ms 262144 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 221000 KB Ok
2 Correct 449 ms 221000 KB Ok
3 Correct 424 ms 221068 KB Ok
4 Correct 428 ms 221080 KB Ok
5 Correct 447 ms 221000 KB Ok
6 Correct 654 ms 229072 KB Ok
7 Correct 645 ms 229960 KB Ok
8 Correct 796 ms 231372 KB Ok
9 Correct 701 ms 231496 KB Ok
10 Correct 598 ms 225864 KB Ok
11 Correct 668 ms 231668 KB Ok

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 221256 KB Ok
2 Correct 458 ms 221000 KB Ok
3 Correct 455 ms 221000 KB Ok
4 Correct 433 ms 221072 KB Ok
5 Correct 433 ms 221256 KB Ok
6 Correct 450 ms 221000 KB Ok
7 Correct 454 ms 221000 KB Ok
8 Correct 451 ms 221000 KB Ok
9 Correct 429 ms 221000 KB Ok
10 Correct 455 ms 223560 KB Ok
11 Correct 445 ms 221072 KB Ok
12 Correct 459 ms 221000 KB Ok
13 Correct 313 ms 221056 KB Ok
14 Correct 497 ms 221008 KB Ok
15 Runtime error 544 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 221256 KB Ok
2 Correct 458 ms 221000 KB Ok
3 Correct 455 ms 221000 KB Ok
4 Correct 433 ms 221072 KB Ok
5 Correct 433 ms 221256 KB Ok
6 Correct 450 ms 221000 KB Ok
7 Correct 454 ms 221000 KB Ok
8 Correct 451 ms 221000 KB Ok
9 Correct 429 ms 221000 KB Ok
10 Correct 455 ms 223560 KB Ok
11 Correct 445 ms 221072 KB Ok
12 Correct 459 ms 221000 KB Ok
13 Runtime error 585 ms 262144 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 221256 KB Ok
2 Correct 458 ms 221000 KB Ok
3 Correct 455 ms 221000 KB Ok
4 Correct 433 ms 221072 KB Ok
5 Correct 433 ms 221256 KB Ok
6 Correct 450 ms 221000 KB Ok
7 Correct 454 ms 221000 KB Ok
8 Correct 451 ms 221000 KB Ok
9 Correct 429 ms 221000 KB Ok
10 Correct 455 ms 223560 KB Ok
11 Correct 445 ms 221072 KB Ok
12 Correct 459 ms 221000 KB Ok
13 Runtime error 585 ms 262144 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -