oj.uz

답안 #58638

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
58638 2018-07-18T14:37:57 Z Benq Nice sequence (IZhO18_sequence) C++14
0 / 100
 13 ms 9904 KB 
#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 << " ";
    exit(0);
}

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
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 13 ms 6648 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 6700 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 6992 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 9904 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 13 ms 6648 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 13 ms 6648 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 13 ms 6648 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -