제출 #382785

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
382785		maximath_1	Nice sequence (IZhO18_sequence)	C++11	100 / 100	1936 ms	36164 KiB

sequence

#include <stdio.h>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string.h>
#include <numeric>
#include <queue>
#include <assert.h>
#include <map>
#include <set>
#include <limits.h>
using namespace std;

#define ll long long
#define ld long double
const int MX = 200005;
const int LG = (int)log2(MX) + 2;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;

#define gc getchar//_unlocked //can't for window server
void cin(int &x){
	char c = gc(); bool neg = false;
	for(; c < '0'||'9' < c; c = gc())
		if(c == '-') neg=true;
	x = c - '0'; c = gc();
	for(; '0' <= c && c <= '9'; c = gc())
		x = (x << 1) + (x << 3) + (c - '0');
	if(neg) x = -x;
}

int tc, n, m;

pair<bool, vector<int> > check(int len){
	vector<int> deg(len + 1, 0);

	for(int i = 0; i <= len; i ++){
		if(i - n >= 0) deg[i - n] ++;
		if(i + m <= len) deg[i + m] ++;
	}

	vector<int> pref(len + 1, 0);
	queue<int> q;
	for(int i = 0; i <= len; i ++){
		if(deg[i] == 0)
			q.push(i);
	}

	int cnt = 0;
	for(; q.size();){
		int nw = q.front(); q.pop();
		pref[nw] = ++ cnt;

		if(nw - n >= 0){
			deg[nw - n] --;
			if(deg[nw - n] == 0)
				q.push(nw - n);
		}

		if(nw + m <= len){
			deg[nw + m] --;
			if(deg[nw + m] == 0)
				q.push(nw + m);
		}
	}

	bool valid = 1;
	for(int i = 0; i <= len; i ++)
		if(deg[i] > 0) valid = 0;

	vector<int> res(len, 0);
	for(int i = 0; i < len; i ++)
		res[i] = pref[i + 1] - pref[i];

	return make_pair(valid, res);
}

int main(){
	cin(tc);

	for(; tc --;){
		cin(n); cin(m);

		int lf = max(n, m) - 1, rg = n + m, rs = lf;
		vector<int> ans(rs, -1);
		if(n > m) ans = vector<int>(rs, 1);

		for(int md; lf <= rg;){
			md = (lf + rg) / 2;
			pair<bool, vector<int> > get = check(md);
			if(get.first){
				ans = get.second;
				rs = md;
				lf = md + 1;
			}else{
				rg = md - 1;
			}
		}

		printf("%d\n", rs);
		for(int i = 0; i < rs; i ++)
			printf("%d ", ans[i]);
		printf("\n");
	}
	
	return 0;
}

• 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