fork download
  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
stdin
Standard input is empty
stdout
Standard output is empty