fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. typedef long double ld;
  6. typedef double db; 
  7. typedef string str; 
  8.  
  9. typedef pair<int,int> pi;
  10. typedef pair<ll,ll> pl; 
  11. typedef pair<db,db> pd; 
  12.  
  13. typedef vector<int> vi; 
  14. typedef vector<bool> vb; 
  15. typedef vector<ll> vl; 
  16. typedef vector<db> vd; 
  17. typedef vector<str> vs; 
  18. typedef vector<pi> vpi;
  19. typedef vector<pl> vpl; 
  20. typedef vector<pd> vpd; 
  21.  
  22. #define mp make_pair
  23. #define f first
  24. #define s second
  25. #define sz(x) (int)(x).size()
  26. #define all(x) begin(x), end(x)
  27. #define rall(x) (x).rbegin(), (x).rend() 
  28. #define sor(x) sort(all(x)) 
  29. #define rsz resize
  30. #define ins insert 
  31. #define ft front() 
  32. #define bk back()
  33. #define pf push_front 
  34. #define pb push_back
  35. #define eb emplace_back 
  36. #define lb lower_bound 
  37. #define ub upper_bound 
  38.  
  39. #define FOR(i,a,b) for (int i = (a); i < (b); ++i)
  40. #define F0R(i,a) FOR(i,0,a)
  41. #define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
  42. #define R0F(i,a) ROF(i,0,a)
  43. #define trav(a,x) for (auto& a: x)
  44.  
  45. const int MOD = 1e9+7; // 998244353;
  46. const int MX = 2e5+5; 
  47. const ll INF = 1e18; 
  48. const ld PI = acos((ld)-1);
  49. const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1}; 
  50. mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 
  51.  
  52. template<class T> bool ckmin(T& a, const T& b) { 
  53. 	return b < a ? a = b, 1 : 0; }
  54. template<class T> bool ckmax(T& a, const T& b) { 
  55. 	return a < b ? a = b, 1 : 0; } 
  56. constexpr int pct(int x) { return __builtin_popcount(x); } 
  57. constexpr int bits(int x) { return 31-__builtin_clz(x); } // floor(log2(x)) 
  58. ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
  59. ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down
  60. ll half(ll x) { return fdiv(x,2); }
  61.  
  62. template<class T, class U> T fstTrue(T lo, T hi, U f) { 
  63. 	// note: if (lo+hi)/2 is used instead of half(lo+hi) then this will loop infinitely when lo=hi
  64. 	hi ++; assert(lo <= hi); // assuming f is increasing
  65. 	while (lo < hi) { // find first index such that f is true 
  66. 		T mid = half(lo+hi);
  67. 		f(mid) ? hi = mid : lo = mid+1; 
  68. 	} 
  69. 	return lo;
  70. }
  71. template<class T, class U> T lstTrue(T lo, T hi, U f) {
  72. 	lo --; assert(lo <= hi); // assuming f is decreasing
  73. 	while (lo < hi) { // find first index such that f is true 
  74. 		T mid = half(lo+hi+1);
  75. 		f(mid) ? lo = mid : hi = mid-1;
  76. 	} 
  77. 	return lo;
  78. }
  79. template<class T> void remDup(vector<T>& v) { 
  80. 	sort(all(v)); v.erase(unique(all(v)),end(v)); }
  81.  
  82. // INPUT
  83. template<class A> void re(complex<A>& c);
  84. template<class A, class B> void re(pair<A,B>& p);
  85. template<class A> void re(vector<A>& v);
  86. template<class A, size_t SZ> void re(array<A,SZ>& a);
  87.  
  88. template<class T> void re(T& x) { cin >> x; }
  89. void re(db& d) { str t; re(t); d = stod(t); }
  90. void re(ld& d) { str t; re(t); d = stold(t); }
  91. template<class H, class... T> void re(H& h, T&... t) { re(h); re(t...); }
  92.  
  93. template<class A> void re(complex<A>& c) { A a,b; re(a,b); c = {a,b}; }
  94. template<class A, class B> void re(pair<A,B>& p) { re(p.f,p.s); }
  95. template<class A> void re(vector<A>& x) { trav(a,x) re(a); }
  96. template<class A, size_t SZ> void re(array<A,SZ>& x) { trav(a,x) re(a); }
  97.  
  98. // TO_STRING
  99. #define ts to_string
  100. str ts(char c) { return str(1,c); }
  101. str ts(const char* s) { return (str)s; }
  102. str ts(str s) { return s; }
  103. str ts(bool b) { 
  104. 	#ifdef LOCAL
  105. 		return b ? "true" : "false"; 
  106. 	#else 
  107. 		return ts((int)b);
  108. 	#endif
  109. }
  110. template<class A> str ts(complex<A> c) { 
  111. 	stringstream ss; ss << c; return ss.str(); }
  112. str ts(vector<bool> v) {
  113. 	str res = "{"; F0R(i,sz(v)) res += char('0'+v[i]);
  114. 	res += "}"; return res; }
  115. template<size_t SZ> str ts(bitset<SZ> b) {
  116. 	str res = ""; F0R(i,SZ) res += char('0'+b[i]);
  117. 	return res; }
  118. template<class A, class B> str ts(pair<A,B> p);
  119. template<class T> str ts(T v) { // containers with begin(), end()
  120. 	#ifdef LOCAL
  121. 		bool fst = 1; str res = "{";
  122. 		for (const auto& x: v) {
  123. 			if (!fst) res += ", ";
  124. 			fst = 0; res += ts(x);
  125. 		}
  126. 		res += "}"; return res;
  127. 	#else
  128. 		bool fst = 1; str res = "";
  129. 		for (const auto& x: v) {
  130. 			if (!fst) res += " ";
  131. 			fst = 0; res += ts(x);
  132. 		}
  133. 		return res;
  134.  
  135. 	#endif
  136. }
  137. template<class A, class B> str ts(pair<A,B> p) {
  138. 	#ifdef LOCAL
  139. 		return "("+ts(p.f)+", "+ts(p.s)+")"; 
  140. 	#else
  141. 		return ts(p.f)+" "+ts(p.s);
  142. 	#endif
  143. }
  144.  
  145. // OUTPUT
  146. template<class A> void pr(A x) { cout << ts(x); }
  147. template<class H, class... T> void pr(const H& h, const T&... t) { 
  148. 	pr(h); pr(t...); }
  149. void ps() { pr("\n"); } // print w/ spaces
  150. template<class H, class... T> void ps(const H& h, const T&... t) { 
  151. 	pr(h); if (sizeof...(t)) pr(" "); ps(t...); }
  152.  
  153. // DEBUG
  154. void DBG() { cerr << "]" << endl; }
  155. template<class H, class... T> void DBG(H h, T... t) {
  156. 	cerr << ts(h); if (sizeof...(t)) cerr << ", ";
  157. 	DBG(t...); }
  158. #ifdef LOCAL // compile with -DLOCAL, chk -> fake assert
  159. 	#define dbg(...) cerr << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
  160. 	#define chk(...) if (!(__VA_ARGS__)) cerr << "Line(" << __LINE__ << ") -> function(" \
  161. 		 << __FUNCTION__  << ") -> CHK FAILED: (" << #__VA_ARGS__ << ")" << "\n", exit(0);
  162. #else
  163. 	#define dbg(...) 0
  164. 	#define chk(...) 0
  165. #endif
  166.  
  167. // FILE I/O
  168. void setIn(str s) { freopen(s.c_str(),"r",stdin); }
  169. void setOut(str s) { freopen(s.c_str(),"w",stdout); }
  170. void unsyncIO() { cin.tie(0)->sync_with_stdio(0); }
  171. void setIO(str s = "") {
  172. 	unsyncIO();
  173. 	// cin.exceptions(cin.failbit); 
  174. 	// throws exception when do smth illegal
  175. 	// ex. try to read letter into int
  176. 	if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
  177. }
  178.  
  179.  
  180. #include "fun.h"
  181.  
  182. vi adj[MX];
  183. int color[MX];
  184. vpi vis;
  185.  
  186. void dfs(int a, int b, int d) {
  187. 	vis.pb({d,a});
  188. 	trav(t,adj[a]) if (t != b) dfs(t,a,d+1);
  189. }
  190.  
  191. std::vector<int> createFunTour(int N, int Q) {
  192. 	F0R(i,N) FOR(j,i+1,N) {
  193. 		if (hoursRequired(i,j) == 1) {
  194. 			adj[i].pb(j), adj[j].pb(i);
  195. 		}
  196. 	}
  197. 	F0R(i,N) {
  198. 		int maxSize = 0;
  199. 		vector<vpi> tmp;
  200. 		trav(t,adj[i]) {
  201. 			vis.clear(); dfs(t,i,1);
  202. 			ckmax(maxSize,sz(vis));
  203. 			tmp.pb(vis);
  204. 		}
  205. 		if (2*maxSize > N) continue;
  206. 		color[i] = -1;
  207. 		F0R(_,sz(tmp)) trav(t,tmp[_]) color[t.s] = _;
  208. 		trav(t,tmp) sort(rall(t));
  209. 		vpi res{{0,i}};
  210. 		int lef = N;
  211. 		int col = -1, lst = -1;
  212. 		while (1) {
  213. 			lef --; if (lef == 0) break;
  214. 			pi bes = {MOD,MOD};
  215. 			if (lst == 1) {
  216. 				F0R(_,sz(tmp)) if (_ != col) {
  217. 					if (sz(tmp[_])) ckmin(bes,tmp[_].bk);
  218. 				}
  219. 				res.pb(bes); tmp[color[bes.s]].pop_back();
  220. 				lst ^= 1;
  221. 			} else if (lst == 0) {
  222. 				F0R(_,sz(tmp)) if (_ == col) {
  223. 					if (sz(tmp[_])) ckmin(bes,tmp[_].bk);
  224. 				}
  225. 				res.pb(bes); tmp[color[bes.s]].pop_back();
  226. 				lst ^= 1;
  227. 			} else {
  228. 				maxSize = 0;
  229. 				F0R(_,sz(tmp)) {
  230. 					ckmax(maxSize,sz(tmp[_]));
  231. 					if (sz(tmp[_]) && _ != color[res.bk.s]) ckmin(bes,tmp[_].bk);
  232. 				}
  233. 				if (2*maxSize > lef) { 
  234. 					trav(t,tmp) if (sz(t) == maxSize) {
  235. 						bes = t.bk;
  236. 						res.pb(bes);
  237. 						col = color[bes.s];
  238. 						tmp[color[bes.s]].pop_back();
  239. 					}
  240. 					lst = 1;
  241. 					continue;
  242. 				} 
  243. 				if (2*maxSize == lef) {
  244. 					int big = 0; F0R(i,sz(tmp)) if (sz(tmp[i]) == maxSize) big = i;
  245. 					pi x = tmp[big].bk, y = {MOD,MOD};
  246. 					F0R(i,sz(tmp)) if (i != big && sz(tmp[i])) ckmin(y,tmp[i].bk);
  247. 					pi one = res.bk, two = {-MOD,-MOD};
  248. 					if (sz(res) > 1) two = res[sz(res)-2];
  249. 					if (color[x.s] != color[res.bk.s] && x >= two && y >= one) {
  250. 						res.pb(x); col = color[x.s]; lst = 1;
  251. 						tmp[color[x.s]].pop_back();
  252. 						continue;
  253. 					}
  254. 					if (color[y.s] != color[res.bk.s] && y >= two && x >= one) {
  255. 						res.pb(y); col = color[x.s]; lst = 0;
  256. 						tmp[color[y.s]].pop_back();
  257. 						continue;
  258. 					}
  259. 					exit(5); // one of above two cases must hold
  260. 				}
  261. 				res.pb(bes); tmp[color[bes.s]].pop_back(); // just greedy
  262. 			}
  263. 		}
  264. 		FOR(i,2,sz(res)) assert(res[i] >= res[i-2]);
  265. 		FOR(i,1,sz(res)) assert(color[res[i].s] != color[res[i-1].s]);
  266. 		reverse(all(res));
  267. 		vi ans; trav(t,res) ans.pb(t.s);
  268. 		return ans;
  269. 	}
  270. 	return {};
  271. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:180:10: fatal error: fun.h: No such file or directory
 #include "fun.h"
          ^~~~~~~
compilation terminated.
stdout
copy 
Standard output is empty
https://ideone.com/QTszhX
APIO 2020 C
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!