oj.uz

답안 #1114120

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1114120 2024-11-18T08:12:21 Z vjudge1 Nice sequence (IZhO18_sequence) C++17
21 / 100
 473 ms 181064 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 = 2000001;
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

# 결과 실행 시간 메모리 Grader output
1 Correct 189 ms 89416 KB Ok
2 Correct 180 ms 89420 KB Ok
3 Correct 152 ms 89420 KB Ok
4 Correct 153 ms 89392 KB Ok
5 Correct 156 ms 89436 KB Ok
6 Correct 167 ms 89344 KB Ok
7 Correct 154 ms 89416 KB Ok
8 Correct 157 ms 89356 KB Ok
9 Correct 159 ms 89412 KB Ok
10 Correct 163 ms 89416 KB Ok
11 Correct 163 ms 89416 KB Ok
12 Correct 167 ms 89272 KB Ok

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 215 ms 181064 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 118 ms 89424 KB Ok
2 Correct 187 ms 89416 KB Ok
3 Runtime error 217 ms 181016 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #4
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 201 ms 89280 KB Ok
2 Correct 178 ms 89420 KB Ok
3 Correct 171 ms 89416 KB Ok
4 Correct 165 ms 89508 KB Ok
5 Correct 171 ms 89460 KB Ok
6 Correct 348 ms 97324 KB Ok
7 Correct 343 ms 98380 KB Ok
8 Correct 473 ms 99912 KB Ok
9 Correct 383 ms 99852 KB Ok
10 Correct 301 ms 94124 KB Ok
11 Correct 397 ms 99792 KB Ok

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 189 ms 89416 KB Ok
2 Correct 180 ms 89420 KB Ok
3 Correct 152 ms 89420 KB Ok
4 Correct 153 ms 89392 KB Ok
5 Correct 156 ms 89436 KB Ok
6 Correct 167 ms 89344 KB Ok
7 Correct 154 ms 89416 KB Ok
8 Correct 157 ms 89356 KB Ok
9 Correct 159 ms 89412 KB Ok
10 Correct 163 ms 89416 KB Ok
11 Correct 163 ms 89416 KB Ok
12 Correct 167 ms 89272 KB Ok
13 Correct 118 ms 89424 KB Ok
14 Correct 187 ms 89416 KB Ok
15 Runtime error 217 ms 181016 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 189 ms 89416 KB Ok
2 Correct 180 ms 89420 KB Ok
3 Correct 152 ms 89420 KB Ok
4 Correct 153 ms 89392 KB Ok
5 Correct 156 ms 89436 KB Ok
6 Correct 167 ms 89344 KB Ok
7 Correct 154 ms 89416 KB Ok
8 Correct 157 ms 89356 KB Ok
9 Correct 159 ms 89412 KB Ok
10 Correct 163 ms 89416 KB Ok
11 Correct 163 ms 89416 KB Ok
12 Correct 167 ms 89272 KB Ok
13 Runtime error 215 ms 181064 KB Execution killed with signal 6
14 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 189 ms 89416 KB Ok
2 Correct 180 ms 89420 KB Ok
3 Correct 152 ms 89420 KB Ok
4 Correct 153 ms 89392 KB Ok
5 Correct 156 ms 89436 KB Ok
6 Correct 167 ms 89344 KB Ok
7 Correct 154 ms 89416 KB Ok
8 Correct 157 ms 89356 KB Ok
9 Correct 159 ms 89412 KB Ok
10 Correct 163 ms 89416 KB Ok
11 Correct 163 ms 89416 KB Ok
12 Correct 167 ms 89272 KB Ok
13 Runtime error 215 ms 181064 KB Execution killed with signal 6
14 Halted 0 ms 0 KB -