제출 #1114151

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1114151		vjudge1	Nice sequence (IZhO18_sequence)	C++17	43 / 100	2081 ms	36424 KiB

sequence

//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();
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 6
• Subtask 2: 9 / 9
• Subtask 3: 14 / 14
• Subtask 4: 0 / 15
• Subtask 5: 14 / 14
• Subtask 6: 0 / 18
• Subtask 7: 0 / 24