Submission #58639

#	Time	Username	Problem	Language	Result	Execution time	Memory
58639		Benq	Nice sequence (IZhO18_sequence)	C++14	100 / 100	1423 ms	40120 KiB

sequence

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 400001;


template<int SZ> struct DSU {
    int par[SZ], sz[SZ], numComp = 0;
    DSU() {
        F0R(i,SZ) par[i] = i, sz[i] = 1;
    }
    
    int get(int x) { // path compression
    	if (par[x] != x) par[x] = get(par[x]);
    	return par[x];
    }
    
    bool unite(int x, int y) { // union-by-rank
    	x = get(x), y = get(y);
    	if (x == y) return 0;
    	numComp --;
    	if (sz[x] < sz[y]) swap(x,y);
    	sz[x] += sz[y], par[y] = x;
    	return 1;
    }
};

DSU<MX> D;

int T;

int N,M; 

void test(int x) {
    D.numComp ++;
    if (x > N) D.unite(x-N,x);
    if (x > M) D.unite(x-M,x);
}


vi flip(vi z) {
    F0R(i,sz(z)) z[i] *= -1;
    return z;
}
 
vi triN(int N, vi z) {
    if (sz(z) < N) return z;
    int tmp = 0; F0R(i,N) tmp += z[i];
    if (tmp > 0) z = flip(z);
    return z;
}
 
vi triM(int N, vi z) {
    if (sz(z) < N) return z;
    int tmp = 0; F0R(i,N) tmp += z[i];
    if (tmp < 0) z = flip(z);
    return z;
}


void solve() {
    cin >> N >> M; 
    // N = 8, M = 6;
    vi res;
    if (max(N,M) % min(N,M) == 0) {
        F0R(i,max(N,M)-1) res.pb(1);
    } else {
        D = DSU<400001>();
        int RES = 0;
        FOR(i,1,400001) {
            test(i);
            if (i > __gcd(N,M) && D.numComp == __gcd(N,M)) {
                RES = i-1;
                break;
            }
        }
        D = DSU<400001>();
        FOR(i,1,RES+1) test(i);
        FOR(i,1,RES+1) if (D.get(i) == D.get(RES+1-M)) res.pb(1);
        else res.pb(-1);
        pi x = {0,0}, y = {0,0};
        F0R(i,N) if (res[i] == 1) x.f ++; else x.s ++;
        F0R(i,M) if (res[i] == 1) y.f ++; else y.s ++;
        F0R(i,sz(res)) {
            if (res[i] == 1) res[i] *= x.s+y.s;
            else res[i] *= x.f+y.f;
        }
    }
    res = triN(N,res);
    res = triM(M,res);
    cout << sz(res) << "\n";
    for (int i: res) cout << i << " ";
    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> T;
    F0R(i,T) solve();
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

• 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