제출 #46516

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
46516		Bruteforceman	Nice sequence (IZhO18_sequence)	C++11	76 / 100	314 ms	31948 KiB

sequence

#include "bits/stdc++.h"
using namespace std;
int N, M;
vector <int> g[400010];
int solution[400010], pref[400010];
int deg[400010];
int v[400010];

bool good(int size) {
	for(int i = 0; i <= size; i++) {
		g[i].clear();
		deg[i] = 0;
	}
	for(int i = N; i <= size; i++) {
		g[i].push_back(i - N);
		++deg[i - N];
	}
	for(int i = 0; i <= size - M; i++) {
		g[i].push_back(i + M);
		++deg[i + M];
	}
	queue <int> Q;
	for(int i = 0; i <= size; i++) {
		if(deg[i] == 0) {
			Q.push(i);
		}
	}
	int cnt = 0;
	while(!Q.empty()) {
		int x = Q.front();
		Q.pop();
		cnt++;
		for(auto i : g[x]) {
			--deg[i];
			if(deg[i] == 0) {
				Q.push(i);
			}
		}
	}
	if(cnt == size + 1) {
		return true;
	}
	return false;
}

void solve(int size) {
	for(int i = 0; i <= size; i++) {
		g[i].clear();
		deg[i] = 0;
	}
	for(int i = N; i <= size; i++) {
		g[i].push_back(i - N);
		++deg[i - N];
	}
	for(int i = 0; i <= size - M; i++) {
		g[i].push_back(i + M);
		++deg[i + M];
	}
	queue <int> Q;
	for(int i = 0; i <= size; i++) {
		if(deg[i] == 0) {
			Q.push(i);
		}
	}
	int cnt = 0;
	while(!Q.empty()) {
		int x = Q.front();
		Q.pop();
		v[cnt++] = x;
		for(auto i : g[x]) {
			--deg[i];
			if(deg[i] == 0) {
				Q.push(i);
			}
		}
	}
	if(cnt == size + 1) {
		for(int i = 0; i < cnt; i++) {
			if(v[i] == 0) {
				int cur = 0;
				for(int j = i-1; j >= 0; j--) {
					pref[v[j]] = --cur; 
				}
				cur = 0;
				for(int j = i+1; j < cnt; j++) {
					pref[v[j]] = ++cur;
				}
				break;
			}
		}
		for(int i = 1; i <= size; i++) {
			solution[i] = pref[i] - pref[i - 1];
		}
	}
}

int search(int b, int e) {
	if(b == e) {
		return b;
	}
	int m = (b + e + 1) >> 1;
	if(good(m)) return search(m, e);
	else return search(b, m - 1);
}

int main(int argc, char const *argv[])
{
	int test;
	scanf("%d", &test);
	for(int cs = 1; cs <= test; cs++) {
		scanf("%d %d", &N, &M);		
		int ans = 0;
		if(N == M) {
			ans = N-1;
		} else if (N > M) {
			int diff = N % M;
			for(int i = 0; i < M; i++) {
				ans = max(ans, (i * diff) % M);
			}
			ans += N - 1;
		} else {
			int diff = M % N;
			for(int i = 0; i < N; i++) {
				ans = max(ans, (i * diff) % N);
			}
			ans += M - 1;
		}
		solve(ans);
		printf("%d\n", ans);
		for(int i = 1; i <= ans; i++) {
			printf("%d ", solution[i]);
		}
		printf("\n");
	}
	return 0; 
}

컴파일 시 표준 에러 (stderr) 메시지

sequence.cpp: In function 'int main(int, const char**)':
sequence.cpp:109:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &test);
  ~~~~~^~~~~~~~~~~~~
sequence.cpp:111:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &N, &M);  
   ~~~~~^~~~~~~~~~~~~~~~~

• 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: 0 / 24