oj.uz

Submission #501408

# Submission time Handle Problem Language Result Execution time Memory
501408 2022-01-03T06:19:48 Z Ziel Nice sequence (IZhO18_sequence) C++17
0 / 100
 2000 ms 9676 KB 
/**
 * 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();
		while (c != '-' && ('0' > c || c > '9')) {
			c = getchar();
		}
		if (c == '-')
			flag = -1, c = getchar();
		while ('0' <= c && c <= '9') {
			x = x * 10 + c - '0';
			c = getchar();
		}
		x *= flag;
	}

	inline void _vout(ll x) {
		if (x) {
			_vout(x / 10);
			putchar(x % 10 + '0');
		}
	}
	inline void vout(ll x) {
		if (x < 0) {
			putchar('-');
			_vout(-x);
		} else if (!x) {
			putchar('0');
		} else {
			_vout(x / 10);
			putchar(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 = 0, 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("");
    
    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(' ');

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

2 1 3 0
*/

signed main() {
    setIO();
    
    int tt = 1;
    if (FLAG) {
    	cin >> 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 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);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2082 ms 9676 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2072 ms 9676 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2079 ms 9676 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2083 ms 9676 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2082 ms 9676 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2082 ms 9676 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2082 ms 9676 KB Time limit exceeded
2 Halted 0 ms 0 KB -