oj.uz

Submission #1114113

# Submission time Handle Problem Language Result Execution time Memory
1114113 2024-11-18T08:04:41 Z vjudge1 Nice sequence (IZhO18_sequence) C++17
0 / 100
 491 ms 223560 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;
        }
    }

    void dfss(int node,const int parent = 1) {
        vis[node] = 1;
        v[node] = parent-1;
        for (auto it : edges[node]) dfss(it,v[node]);
    }
    int dfs(int node) {
        if (vis[node]) return v[node];
        vis[node] = 1;
        int mx = 0;
        for (auto it : edges[node]) {
            mx = max(mx,dfs(it));
        }
        return v[node] = mx+1;
    }
    void solve() {
        for (int i = 1;i<=nd;i++) vis[i] = 0;
        dfss(0);
        for (int i = 1;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++) 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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 491 ms 221000 KB Ok
2 Incorrect 438 ms 221000 KB All the numbers must be nonzero
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 467 ms 221060 KB All the numbers must be nonzero
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 220876 KB Ok
2 Correct 465 ms 222836 KB Ok
3 Incorrect 475 ms 221000 KB All the numbers must be nonzero
4 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 468 ms 223560 KB All the numbers must be nonzero
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 491 ms 221000 KB Ok
2 Incorrect 438 ms 221000 KB All the numbers must be nonzero
3 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 491 ms 221000 KB Ok
2 Incorrect 438 ms 221000 KB All the numbers must be nonzero
3 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 491 ms 221000 KB Ok
2 Incorrect 438 ms 221000 KB All the numbers must be nonzero
3 Halted 0 ms 0 KB -