Submission #501411

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
501411	2022-01-03T06:26:58 Z	Ziel	Nice sequence (IZhO18_sequence)	C++17	Compilation error	0 ms	0 KB

sequence

/**
 * LES GREATEABLES BRO TEAM
**/

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define sz(x) (int)x.size()
const bool FLAG = true;
void setIO(const string &f = "");

namespace io {
	inline void vin(ll &x) {
		int flag = 1;
		x = 0;
		char c = getchar_unlocked();
		while (c != '-' && ('0' > c || c > '9')) {
			c = getchar_unlocked();
		}
		if (c == '-')
			flag = -1, c = getchar_unlocked();
		while ('0' <= c && c <= '9') {
			x = x * 10 + c - '0';
			c = getchar_unlocked();
		}
		x *= flag;
	}

	inline void _vout(ll x) {
		if (x) {
			_vout(x / 10);
			putchar_unlocked(x % 10 + '0');
		}
	}
	inline void vout(ll x) {
		if (x < 0) {
			putchar_unlocked('-');
			_vout(-x);
		} else if (!x) {
			putchar_unlocked('0');
		} else {
			_vout(x / 10);
			putchar_unlocked(x % 10 + '0');
		}
	}
}
using namespace io;


#define int ll
const int N = 4e5 + 156;
int was[N], visited[N];
vector<int> g[N], order;

inline bool dfs(int v) {
	was[v] = 1;
	for (int to: g[v]) {
		if (!was[to]) {
			if (dfs(to))
				return true;
		} else if (was[to] == 1)
			return true;
	}
	was[v] = 2;
	return false;
}
inline void dfs2(int v) {
	visited[v] = 1;
	for (int to: g[v]) {
		if (!visited[to])
			dfs2(to);
	}
	order.push_back(v);
}

inline void solve() {
    int n, m;
    vin(n);
    vin(m);

    int lo = min(n, m) - 1, hi = n + m, res = -1;
    while (lo <= hi) {
    	int mid = (lo + hi) / 2;

		for (int i = n; i <= mid; i++)
			g[i].push_back(i - n);
		for (int i = m; i <= mid; i++)
			g[i - m].push_back(i);

		bool have_cycle = false;
		for (int i = 0; i <= mid; i++) {
			if (!was[i] && dfs(i)) {
				have_cycle = true;
				break;
			}
		}
		for (int i = 0; i <= mid; i++) {
			was[i] = 0;
			if (sz(g[i])) g[i].clear();
		}

		if (have_cycle) {
			hi = mid - 1;
		} else {
			lo = mid + 1;
			res = mid;
		}
    }
    vout(res);
    puts_unlocked("");
    
    for (int i = n; i <= res; i++)
		g[i].push_back(i - n);
	for (int i = m; i <= res; i++)
		g[i - m].push_back(i);
    for (int i = 0; i <= res; i++) {
    	if (!visited[i])
    		dfs2(i);
    }
    reverse(order.begin(), order.end());
    vector<int> p(sz(order));
    for (int i = 0; i < sz(order); i++) {
    	p[order[i]] = i;
   	}
   	int x = p[0];
   	for (int i = 0; i < sz(p); i++)
   		p[i] -= x;
   	for (int i = 1; i < sz(p); i++)
   		vout(p[i] - p[i - 1]), putchar_unlocked(' ');

   	order.clear();
   	for (int i = 0; i <= res; i++) {
		was[i] = 0;
		visited[i] = 0;
		if (sz(g[i])) g[i].clear();
	}
	puts_unlocked("");
}
/*
0 2
1 3
3 0

2 1 3 0
*/

signed main() {
//    setIO();
    
    int tt = 1;
    if (FLAG) {
    	vin(tt);
    }
    while (tt--) {
    	solve();
    }
    
    return 0;
}

void setIO(const string &f) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen((f + ".in").c_str(), "r")) {
        freopen((f + ".in").c_str(), "r", stdin);
        freopen((f + ".out").c_str(), "w", stdout);
    }
}

Compilation message

sequence.cpp: In function 'void solve()':
sequence.cpp:112:5: error: 'puts_unlocked' was not declared in this scope; did you mean 'fputs_unlocked'?
  112 |     puts_unlocked("");
      |     ^~~~~~~~~~~~~
      |     fputs_unlocked
sequence.cpp: In function 'void setIO(const string&)':
sequence.cpp:167:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |         freopen((f + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:168:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  168 |         freopen((f + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~