Submission #676872

#	Time	Username	Problem	Language	Result	Execution time	Memory
676872		YENGOYAN	Nice sequence (IZhO18_sequence)	C++17	76 / 100	2067 ms	38760 KiB

sequence

/*
	//\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\\
	\\                                    //
	//  271828___182845__904523__53602__  \\
	\\  87___47____13______52____66__24_  //
	//  97___75____72______47____09___36  \\
	\\  999595_____74______96____69___67  //
	//  62___77____24______07____66__30_  \\
	\\  35___35____47______59____45713__  //
	//                                    \\
	\\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\//
											  */

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_map>
#include <cmath>
#include <climits>
#include <algorithm>
#include <random>
#include <queue>
#include <deque>
#include <iomanip>
#include <string>
#include <tuple>
#include <bitset>
#include <chrono>
#include <ctime>
#include <fstream>
#include <stack>
#include <cstdio>

using namespace std;
using ll = long long;
const int N = 1e5 + 5;
const ll mod = 1e9 + 7, inf = 1e12;

vector<bool> vis;
vector<vector<int>> gp;
vector<int> order;

void dfs(int u) {
	if (u >= vis.size()) {
		cout << "Co sik apushe im arev!\n";
		return;
	}
	vis[u] = 1;
	for (int& v : gp[u]) {
		if (!vis[v]) {
			dfs(v);
		}
	}
	order.push_back(u);
}

int gcd(int a, int b) {
	while (b) {
		a %= b;
		swap(a, b);
	}
	return a;
}

vector<int> top_order(int mid, int n, int m) {
	++mid;
	gp = vector<vector<int>> (mid);
	vis = vector<bool> (mid);
	for (int i = n; i < mid; ++i) gp[i].push_back(i - n);
	for (int i = m; i < mid; ++i) gp[i - m].push_back(i);
	order.clear();
	for (int i = 0; i < mid; ++i) {
		if (!vis[i]) dfs(i);
	}

	reverse(order.begin(), order.end());
	vector<int> pref(mid);
	for (int i = 0; i < order.size(); ++i) pref[order[i]] = i;
	//return {};
	vector<int> ans;
	for (int i = 1; i < mid; ++i) ans.push_back(pref[i] - pref[i - 1]);
	return ans;
}

bool isok(vector<int>& v, int n, int m) {
	ll s = 0;
	if (v.size() < m || v.size() < n) return 1;
	for (int i = 0; i < n; ++i) s += v[i];
	if (s >= 0) return 0;
	for (int i = n; i < v.size(); ++i) {
		s -= v[i - n], s += v[i];
		if (s >= 0) return 0;
	}
	s = 0;
	for (int i = 0; i < m; ++i) s += v[i];
	if (s <= 0) return 0;
	for (int i = m; i < v.size(); ++i) {
		s -= v[i - m], s += v[i];
		if (s <= 0) return 0;
	}
	return 1;
}

void solve() {
	int n, m; cin >> n >> m;
	int  l = 0, r = n + m;
	vector<int> ans;
	while (l + 1 < r) {
		int mid = (l + r) / 2;
		vector<int> v = top_order(mid, n, m);
		if (isok(v, n, m)) l = mid, ans = v;
		else r = mid;
	}
	//cout << l << "\n";
	cout << ans.size() << "\n";
	for (int i = 0; i < ans.size(); ++i) cout << ans[i] << " ";
	cout << "\n";
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	int _; cin >> _; while (_--)
		solve();
}

Compilation message (stderr)

sequence.cpp: In function 'void dfs(int)':
sequence.cpp:46:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  if (u >= vis.size()) {
      |      ~~^~~~~~~~~~~~~
sequence.cpp: In function 'std::vector<int> top_order(int, int, int)':
sequence.cpp:80:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |  for (int i = 0; i < order.size(); ++i) pref[order[i]] = i;
      |                  ~~^~~~~~~~~~~~~~
sequence.cpp: In function 'bool isok(std::vector<int>&, int, int)':
sequence.cpp:89:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   89 |  if (v.size() < m || v.size() < n) return 1;
      |      ~~~~~~~~~^~~
sequence.cpp:89:31: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   89 |  if (v.size() < m || v.size() < n) return 1;
      |                      ~~~~~~~~~^~~
sequence.cpp:92:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |  for (int i = n; i < v.size(); ++i) {
      |                  ~~^~~~~~~~~~
sequence.cpp:99:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |  for (int i = m; i < v.size(); ++i) {
      |                  ~~^~~~~~~~~~
sequence.cpp: In function 'void solve()':
sequence.cpp:118:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |  for (int i = 0; i < ans.size(); ++i) cout << ans[i] << " ";
      |                  ~~^~~~~~~~~~~~

• 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