Language: C++

netman

TLE

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
const ld EPS = 1e-11;
const ld PI = acos(-1.0);
const int INF = (int)1e9 + 5;
const ll LINF = (ll)1e18 + 5;
 
template<class T> 
ll abs(const T & x) { return x < 0 ? -x : x; }
 
template<class T> 
ll round(const T & x) { return x < 0 ? x - 0.5 : x + 0.5; }
 
template<class T> 
bool chmin(T & x, const T & y) {
	if (y < x) {
		x = y;
		return true;
	}
	return false;
}
 
template<class T> 
bool chmax(T & x, const T & y) {
	if (x < y) {
		x = y;
		return true;
	}
	return false;
}
 
#define all(a) (a).begin(), (a).end()
 
const int N = 100100;
 
int n;
int p[N], sz[N], tp[N], tsz[N];
int cnt, tcnt;
 
void init() {
	for (int i = 1; i <= n; i++) {
		p[i] = i;
		sz[i] = 1;
	}
	cnt = n;
}
 
int get(int x) {
	if (x == p[x]) return x;
	return p[x] = get(p[x]);
}
 
bool unite(int x, int y) {
	x = get(x);
	y = get(y);
	if (x == y) return false;
	if (sz[x] > sz[y]) swap(x, y);
	sz[y] += sz[x];
	p[x] = y;
	cnt--;
	return true;
}
 
vector<int> generate() {
	int cnt = rand() % min(n, 1000) + 1;
	static vector<int> res;
	res.resize(cnt);
	static vector<int> perm(n);
	for (int i = 0; i < n; i++) {
		perm[i] = i + 1;
	}
	random_shuffle(all(perm));
	sort(perm.begin(), perm.begin() + cnt);
	int l = 0;
	perm[cnt - 1] = n;
	for (int i = 0; i < cnt; i++) {
		res[i] = perm[i] - l;
		l = perm[i];
	}
	return res;
}
 
void check(const vector<int> & a, vector<int> & b) {
	static int iterNum = 0;
	memcpy(p, tp, sizeof(p[0]) * (n + 1));
	memcpy(sz, tsz, sizeof(sz[0]) * (n + 1));
	cnt = tcnt;
	
	int st = 1;
	for (int & x : b) {
		int l = st;
		int r = l + x - 1;
		while (l < r) {
			unite(l, r);
			l++; r--;
		}
		st += x;
	}
	if (cnt == 1) {
		for (const int & x : a) {
			printf("%d ", x);
		}
		puts("");
		printf("%d\n", (int)b.size());
		for (int & x : b) {
			printf("%d ", x);
		}
		puts("");
		exit(0);
	}
 
}
 
void iteration(const vector<int> & a) {
	static int iterNum = 0;
	memcpy(p, tp, sizeof(p[0]) * (n + 1));
	memcpy(sz, tsz, sizeof(sz[0]) * (n + 1));
	cnt = tcnt;
	
	vector<int> b = generate();
 
	int st = 1;
	for (int & x : b) {
		int l = st;
		int r = l + x - 1;
		while (l < r) {
			unite(l, r);
			l++; r--;
		}
		st += x;
	}
	if (cnt == 1) {
		for (const int & x : a) {
			printf("%d ", x);
		}
		puts("");
		printf("%d\n", (int)b.size());
		for (int & x : b) {
			printf("%d ", x);
		}
		puts("");
		exit(0);
	}
}
 
int main() {
#ifdef LOCAL 
	freopen("input.txt", "r", stdin);
#else
#endif
 
	int m;
 
	cin >> n >> m;
	vector<int> a(m);
 
	for (int & x : a) {
		cin >> x;	
	}
 
	for (int outerIter = 0; outerIter < 10; outerIter++) {
 
	random_shuffle(all(a));
 
	int st = 1;
 
	init();
 
	for (int & x : a) {
		int l = st;
		int r = l + x - 1;
		while (l < r) {
			unite(l, r);
			l++; r--;
		}
		st += x;
	}
 
	memcpy(tp, p, sizeof(p[0]) * (n + 1));
	memcpy(tsz, sz, sizeof(sz[0]) * (n + 1));
	tcnt = cnt;
 
	int iter = (int)1e7 / n / 15;
 
	while (iter--) {
		iteration(a);		
	}
 
	}
 
	for (int z = 0; z < 20; z++) {
		vector<int> b;
		int s = n;
		while (s) {
			if (s == 3) {
				b.push_back(s);
				s = 0;
			}
			else {
				int r = (rand() % 2 == 0 ? 2 : 3);
				b.push_back(r);
				s -= r;
			}
		}
		check(a, b);
	}
 
	puts("Impossible");
 
}


Compiler output:
a.cc:1:1: error: 'netman' does not name a type
    1 | netman
      | ^~~~~~
In file included from /usr/include/c++/14/bits/stl_algobase.h:62,
                 from /usr/include/c++/14/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51,
                 from a.cc:5:
/usr/include/c++/14/ext/type_traits.h:164:35: error: 'constexpr const bool __gnu_cxx::__is_null_pointer' redeclared as different kind of entity
  164 |   __is_null_pointer(std::nullptr_t)
      |                                   ^
/usr/include/c++/14/ext/type_traits.h:159:5: note: previous declaration 'template<class _Type> constexpr bool __gnu_cxx::__is_null_pointer(_Type)'
  159 |     __is_null_pointer(_Type)
      |     ^~~~~~~~~~~~~~~~~
/usr/include/c++/14/ext/type_traits.h:164:26: error: 'nullptr_t' is not a member of 'std'; did you mean 'nullptr_t'?
  164 |   __is_null_pointer(std::nullptr_t)
      |                          ^~~~~~~~~
In file included from /usr/include/c++/14/cstddef:50,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:41:
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:443:29: note: 'nullptr_t' declared here
  443 |   typedef decltype(nullptr) nullptr_t;
      |                             ^~~~~~~~~
In file included from /usr/include/c++/14/bits/stl_pair.h:60,
                 from /usr/include/c++/14/bits/stl_algobase.h:64:
/usr/include/c++/14/type_traits:666:33: error: 'nullptr_t' is not a member of 'std'; did you mean 'nullptr_t'?
  666 |     struct is_null_pointer<std::nullptr_t>
      |                                 ^~~~~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:443:29: note: 'nullptr_t' declared here
  443 |   typedef decltype(nullptr) nullptr_t;
      |                             ^~~~~~~~~
/usr/include/c++/14/type_traits:666:42: error: template argument 1 is invalid
  666 |     struct is_null_pointer<std::nullptr_t>
      |                                          ^
/usr/include/c++/14/type_traits:670:48: error: template argument 1 is invalid
  670 |     struct is_null_pointer<const std::nullptr_t>
      |                                                ^
/usr/include/c++/14/type_traits:674:51: error: template argument 1 is invalid
  674 |     struct is_null_pointer<volatile std::nullptr_t>
      |                                                   ^
/usr/include/c++/14/type_traits:678:57: error: template argument 1 is invalid
  678 |     struct is_null_pointer<const volatile std::nullptr_t>
      |                                                         ^
/usr/include/c++/14/type_traits:1429:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1429 |     : public integral_constant<std::size_t, alignof(_Tp)>
      |                                     ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/type_traits:1429:57: error: template argument 1 is invalid
 1429 |     : public integral_constant<std::size_t, alignof(_Tp)>
      |                                                         ^
/usr/include/c++/14/type_traits:1429:57: note: invalid template non-type parameter
/usr/include/c++/14/type_traits:1438:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1438 |     : public integral_constant<std::size_t, 0> { };
      |                                     ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/type_traits:1438:46: error: template argument 1 is invalid
 1438 |     : public integral_constant<std::size_t, 0> { };
      |                                              ^
/usr/include/c++/14/type_traits:1438:46: note: invalid template non-type parameter
/usr/include/c++/14/type_traits:1440:26: error: 'std::size_t' has not been declared
 1440 |   template<typename _Tp, std::size_t _Size>
      |                          ^~~
/usr/include/c++/14/type_traits:1441:21: error: '_Size' was not declared in this scope
 1441 |     struct rank<_Tp[_Size]>
      |                     ^~~~~
/usr/include/c++/14/type_traits:1441:27: error: template argument 1 is invalid
 1441 |     struct rank<_Tp[_Size]>
      |                           ^
/usr/include/c++/14/type_traits:1442:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1442 |     : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
      |                                     ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/type_traits:1442:65: error: template argument 1 is invalid
 1442 |     : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
      |                                                                 ^
/usr/include/c++/14/type_traits:1442:65: note: invalid template non-type parameter
/usr/include/c++/14/type_traits:1446:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1446 |     : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
      |                                     ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/type_traits:1446:65: error: template argument 1 is invalid
 1446 |     : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
      |                                                                 ^
/usr/include/c++/14/type_traits:1446:65: note: invalid template non-type parameter
/usr/include/c++/14/type_traits:2086:26: error: 'std::size_t' has not been declared
 2086 |   template<typename _Tp, std::size_t _Size>
      |                          ^~~
/usr/include/c++/14/type_traits:2087:30: error: '_Size' was not declared in this scope
 2087 |     struct remove_extent<_Tp[_Size]>
      |                              ^~~~~
/usr/include/c++/14/type_traits:2087:36: error: template argument 1 is invalid
 2087 |     struct remove_extent<_Tp[_Size]>
      |                                    ^
/usr/include/c++/14/type_traits:2099:26: error: 'std::size_t' has not been declared
 2099 |   template<typename _Tp, std::size_t _Size>
      |                          ^~~
/usr/include/c++/14/type_traits:2100:35: error: '_Size' was not declared in this scope
 2100 |     struct remove_all_extents<_Tp[_Size]>
      |                                   ^~~~~
/usr/include/c++/14/type_traits:2100:41: error: template argument 1 is invalid
 2100 |     struct remove_all_extents<_Tp[_Size]>
      |                                         ^
/usr/include/c++/14/type_traits:2171:12: error: 'std::size_t' has not been declared
 2171 |   template<std::size_t _Len>
      |            ^~~
/usr/include/c++/14/type_traits:2176:30: error: '_Len' was not declared in this scope
 2176 |         unsigned char __data[_Len];
      |                              ^~~~
/usr/include/c++/14/type_traits:2194:12: error: 'std::size_t' has not been declared
 2194 |   template<std::size_t _Len, std::size_t _Align =
      |            ^~~
/usr/include/c++/14/type_traits:2194:30: error: 'std::size_t' has not been declared
 2194 |   template<std::size_t _Len, std::size_t _Align =
      |                              ^~~
/usr/include/c++/14/type_traits:2195:55: error: '_Len' was not declared in this scope
 2195 |            __alignof__(typename __aligned_storage_msa<_Len>::__type)>
      |                                                       ^~~~
/usr/include/c++/14/type_traits:2195:59: error: template argument 1 is invalid
 2195 |            __alignof__(typename __aligned_storage_msa<_Len>::__type)>
      |                                                           ^
/usr/include/c++/14/type_traits:2202:30: error: '_Len' was not declared in this scope
 2202 |         unsigned char __data[_Len];
      |                              ^~~~
/usr/include/c++/14/type_traits:2203:44: error: '_Align' was not declared in this scope
 2203 |         struct __attribute__((__aligned__((_Align)))) { } __align;
      |                                            ^~~~~~
In file included from /usr/include/c++/14/bits/stl_tempbuf.h:59,
                 from /usr/include/c++/14/bits/stl_algo.h:69,
                 from /usr/include/c++/14/algorithm:61:
/usr/include/c++/14/new:131:26: error: declaration of 'operator new' as non-function
  131 | _GLIBCXX_NODISCARD void* operator new(std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                          ^~~~~~~~
/usr/include/c++/14/new:131:44: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  131 | _GLIBCXX_NODISCARD void* operator new(std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                                            ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/new:132:41: error: attributes after parenthesized initializer ignored [-fpermissive]
  132 |   __attribute__((__externally_visible__));
      |                                         ^
/usr/include/c++/14/new:133:26: error: declaration of 'operator new []' as non-function
  133 | _GLIBCXX_NODISCARD void* operator new[](std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                          ^~~~~~~~
/usr/include/c++/14/new:133:46: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  133 | _GLIBCXX_NODISCARD void* operator new[](std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                                              ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/new:134:41: error: attributes after parenthesized initializer ignored [-fpermissive]
  134 |   __attribute__((__externally_visible__));
      |                                         ^
/us