fork(3) download
copy 
  1. // Bear and Fair Set, by Errichto
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5. const int K = 5;
  6.  
  7. void NO() {
  8. 	puts("unfair");
  9. 	exit(0);
  10. }
  11.  
  12. int main() {
  13. 	int n, b, q;
  14. 	scanf("%d%d%d", &n, &b, &q);
  15. 	vector<pair<int,int>> w;
  16. 	w.push_back(make_pair(b, n));
  17. 	while(q--) {
  18. 		int a, b;
  19. 		scanf("%d%d", &a, &b);
  20. 		w.push_back(make_pair(a, b));
  21. 	}
  22. 	sort(w.begin(), w.end());
  23. 	// use the Hall's theorem
  24. 	// check all 2^K sets of remainders
  25. 	for(int mask = 0; mask < (1 << K); ++mask) {
  26. 		int at_least = 0, at_most = 0;
  27.  
  28. 		int prev_upto = 0, prev_quan = 0;
  29. 		for(pair<int,int> query : w) {
  30. 			int now_upto = query.first, now_quan = query.second;
  31. 			int places_matching = 0; // how many do give remainder from "mask"
  32. 			int places_other = 0;
  33. 			for(int i = prev_upto + 1; i <= now_upto; ++i) {
  34. 				if(mask & (1 << (i % K)))
  35. 					++places_matching;
  36. 				else
  37. 					++places_other;
  38. 			}
  39. 			if(now_quan < prev_quan) NO();
  40. 			int quan = now_quan - prev_quan;
  41. 			int places_total = now_upto - prev_upto;
  42. 			assert(places_total == places_matching + places_other);
  43. 			if(quan > places_total) NO();
  44.  
  45. 			at_least += max(0, quan - places_other);
  46. 			at_most += min(quan, places_matching);
  47.  
  48. 			prev_upto = now_upto;
  49. 			prev_quan = now_quan;
  50. 		}
  51.  
  52. 		// "mask" represents a set of popcount(mask) remainders
  53. 		// their total degree is (n/K)*popcount(mask)
  54. 		int must_be = n / K * __builtin_popcount(mask);
  55. 		if(!(at_least <= must_be && must_be <= at_most)) NO();
  56. 	}
  57. 	puts("fair");		
  58. 	return 0;
  59. }
  60.  
Time limit exceeded #stdin #stdout 5s 134528KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/IVZ3Ts
Educational Round 8, Bear and Fair Set
language:
C++14 (gcc 8.3)
created:
8 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!