Submission #389775

#	Time	Username	Problem	Language	Result	Execution time	Memory
389775		BartolM	Nice sequence (IZhO18_sequence)	C++17	100 / 100	1557 ms	54748 KiB

sequence

#define DEBUG 1
#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const int N=4e5+5;

int n, m;
vector <int> ls[N]; //(i->j) i veci od j
int in[N], bio[N], sol[N];
queue <int> Q;

void reset(int x) {
    for (int i=0; i<=x; ++i) ls[i].clear(), in[i]=0, bio[i]=0;
}

void build(int x) {
    for (int i=1; i<=x; ++i) {
        if (i-n>=0) ls[i-n].pb(i), in[i]++;
        if (i-m>=0) ls[i].pb(i-m), in[i-m]++;
    }
}

int dfs(int node) {
    if (bio[node]==2) return 0;
    if (bio[node]==1) return 1;
    bio[node]=1;
    int ret=0;
    for (int sus:ls[node]) ret|=dfs(sus);
    bio[node]=2;
    return ret;
}

void topo_sort(int gr) {
    for (int i=0; i<=gr; ++i) if (!in[i]) Q.push(i);
    int curr=gr+1;
    while (!Q.empty()) {
        int node=Q.front();
        Q.pop();
        sol[node]=curr--;
        for (int sus:ls[node]) {
            in[sus]--;
            if (!in[sus]) Q.push(sus);
        }
    }
}

void solve() {
//    int lo=0, hi=2*max(n, m), mid;
//    while (lo<hi) {
//        mid=(lo+hi+1)/2;
//        build(mid);
//        int fl=0;
//        for (int i=0; i<=mid && !fl; ++i) fl+=dfs(i);
//        if (fl) hi=mid-1;
//        else lo=mid;
//        reset(mid);
//    }
    int lo=n+m-__gcd(n, m)-1;
    build(lo);
    topo_sort(lo);
    printf("%d\n", lo);
    for (int i=1; i<=lo; ++i) printf("%d ", sol[i]-sol[i-1]);
    printf("\n");
    reset(lo);
}

void load() {
    scanf("%d %d", &n, &m);
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        load();
        solve();
    }
    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'void load()':
sequence.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   80 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:85:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   85 |     scanf("%d", &t);
      |     ~~~~~^~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 9 / 9
• Subtask 3: 14 / 14
• Subtask 4: 15 / 15
• Subtask 5: 14 / 14
• Subtask 6: 18 / 18
• Subtask 7: 24 / 24