fork download
copy 
  1. #include <cmath>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <iostream>
  5. #include <algorithm>
  6. using namespace std;
  7.  
  8. /* Only Case 38 fails
  9. 3 2 6
  10. 1 1
  11. 1 2
  12. 2 1
  13. 2 2
  14. 3 1
  15. 3 2
  16. */
  17.  
  18. #define MAX_SEATS 1000
  19. #define MAX_CUSTOMERS 2
  20. #define UNKNOWN -1
  21.  
  22. void process (int freq[MAX_SEATS][MAX_CUSTOMERS], int& tickets, int& rides, int& promotions)
  23. {
  24.         rides++;
  25.  
  26.         // find frontmost seat
  27.         int seat1=UNKNOWN;
  28.         int customer1=UNKNOWN;
  29.         for (int i=0; i<MAX_SEATS; i++)
  30.         {
  31.                 if (freq[i][0]>0)
  32.                 {
  33.                         customer1=0;
  34.                         seat1=i;
  35.                         break;
  36.                 }
  37.                 else if (freq[i][1]>0)
  38.                 {
  39.                         customer1=1;
  40.                         seat1=i;
  41.                         break;
  42.                 }
  43.         }
  44.  
  45.         freq[seat1][customer1]--;
  46.         tickets--;
  47.  
  48.         // try to check whether second seat can be selected without promotion
  49.         // find frontmost seat of other customer with multple tickets if available
  50.         // otherwise, find front most seat of other customer with single ticket
  51.         int seat2_freq1=UNKNOWN;
  52.         int seat2_freq_mult=UNKNOWN;
  53.         int customer2=1-customer1;
  54.         for (int i=seat1+1; i<MAX_SEATS; i++)
  55.         {
  56.                 if (freq[i][customer2]>1)
  57.                 {
  58.                         seat2_freq_mult=i;
  59.                         break;
  60.                 }
  61.                 else if ((seat2_freq1==UNKNOWN) && (freq[i][customer2]==1))
  62.                 {
  63.                         seat2_freq1=i;
  64.                 }
  65.         }
  66.  
  67.         if (seat2_freq_mult!=UNKNOWN)
  68.         {
  69.                 freq[seat2_freq_mult][customer2]--;
  70.                 tickets--;
  71.         }
  72.         else if (seat2_freq1!=UNKNOWN)
  73.         {
  74.                 freq[seat2_freq1][customer2]--;
  75.                 tickets--;
  76.         }
  77.         // select second seat using promotion
  78.         else if ((seat1>0)&&(freq[seat1][customer2]>=1))
  79.         {
  80.                 freq[seat1][customer2]--;
  81.                 tickets--;
  82.                 promotions++;
  83.         }
  84. }
  85.  
  86. int main() {
  87.         int t;
  88.         cin >> t;
  89.         for (int i=0; i<t; i++)
  90.         {
  91.                 int seats,customers,tickets;
  92.                 cin >> seats >> customers >> tickets;
  93.                 int freq[MAX_SEATS][MAX_CUSTOMERS]={0};
  94.                 for (int j=0; j<tickets; j++)
  95.                 {
  96.                         int position,buyer;
  97.                         cin >> position >> buyer;
  98.                         // convert from 1-based to 0-based index
  99.                         freq[position-1][buyer-1]++;
  100.                 }
  101.                 int rides=0;
  102.                 int promotions=0;
  103.                 while (tickets>0)
  104.                 {
  105.                         process (freq,tickets,rides,promotions);
  106.                 }
  107.                 printf ("Case #%d: %d %d\n",i+1,rides,promotions);
  108.         }
  109. }
  110.  
Success #stdin #stdout 0s 16064KB
comments (?)
stdin
copy 
1
3 2 6
1 2
1 1
3 1
2 2
2 1
3 2
stdout
copy 
Case #1: 3 1
https://ideone.com/Q6rnSx
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

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!