oj.uz

Submission #879426

# Submission time Handle Problem Language Result Execution time Memory
879426 2023-11-27T10:55:48 Z dimashhh Nice sequence (IZhO18_sequence) C++17
0 / 100
 28 ms 54876 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#pragma GCC optimize("Ofast","O3","unroll-loops")
#pragma GCC target("avx2")
const int N = 1e6 + 10, MOD = 998244353;
int timer = 1,pref[N],n,m,used[N];
vector<int> g[N],ord;
bool ok = false;
void dfs(int v){
    used[v] = 1;
    for(int to:g[v]){
        if(used[to] == 1){
            ok = false;
        }
        if(!used[to]){
            dfs(to);
        }
    }
    used[v] = 2;
    ord.push_back(v);
}
bool can(int len){
  	assert(ok == 1);
    for(int i = 1;i <= len; i++){
        if(i - m >= 0){
            g[i - m].push_back(i);
        }
        if(i - n >= 0){
            g[i].push_back(i - n);
        }
    }
    for(int i = 0;i <= len;i++){
        if(!used[i]){
            dfs(i);
        }
    }
    reverse(ord.begin(),ord.end());
    for(auto i:ord){
        pref[i] = timer++;
    }
    timer = 1;
    ord.clear();
    for(int i = 0;i <= len;i++){
        g[i].clear();
    }
    for(int i = 0;i <= len;i++){
        used[i] = 0;
    }
  	bool ans = ok;
  	ok = 1;
    return ans;
}
void test(){
    cin >> n >> m;
    int l = 0,r = 3e5;
    while(r - l > 1){
        int mid = (l + r) >> 1;
        if(can(mid)){
            l = mid;
        }else{
            r = mid;
        }
    }
    can(l);
    cout << l << '\n';
    for(int i = 1;i <= l;i++){
        cout << pref[i] - pref[i - 1] << ' ';
    }
    cout << '\n';
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    cin >> T;
    for (int i = 1; i <= T; i++)
    {
        test();
    }
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 25 ms 54876 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 28 ms 54876 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 54864 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 54864 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 25 ms 54876 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 25 ms 54876 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 25 ms 54876 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -