fork(1) download
copy 
  1. /*************************************************************************
  2.  * Copyright (C) 2008 by Moustafa Mahmoud (cmpsamurai)                   *
  3.  * moustafa@cmpsamurai.com                                               *
  4.  *************************************************************************/
  5. /*C++ "10037 - Bridge" */
  6.  
  7. #include <algorithm>
  8. #include <cstdio>
  9. #include <cstring>
  10. #include <deque>
  11. #include <fstream>
  12. #include <iostream>
  13. #include <list>
  14. #include <map>
  15. #include <queue>
  16. #include <set>
  17. #include <stack>
  18. #include <string>
  19. #include <vector>
  20. #include <iterator>
  21. #include <sstream>
  22.  
  23. using namespace std;
  24.  
  25. void cross(deque<int> runners)
  26. {
  27.     deque<int> first,second;
  28.     first=runners;
  29.     int time=0;
  30.     stringstream output;
  31.  
  32.     int temp=-1,last1,last2;
  33.  
  34.     while(second.size()<runners.size())
  35.     {
  36.         sort(first.begin(),first.end());
  37.         sort(second.begin(),second.end());
  38.  
  39.         if(first.size()==1)
  40.         {
  41.             output<<first.front()<<endl;
  42.             time+=first.front();
  43.             second.push_front(first.front());
  44.             first.pop_front();
  45.         }
  46.         else if(first.size()==2)
  47.         {
  48.             output<<first[0]<<" "<<first[1]<<endl;
  49.             time+=first[1];
  50.             second.push_back(first.front());
  51.             first.pop_front();
  52.             second.push_back(first.front());
  53.             first.pop_front();
  54.         }
  55.         else if(first.size()==3)
  56.         {
  57.             output<<first[0]<<" "<<first[2]<<endl;
  58.             time+=first[2];
  59.             second.push_back(first[0]);
  60.             second.push_front(first[2]);
  61.             first.pop_front();
  62.             first.pop_back();
  63.             sort(second.begin(),second.end());
  64.             output<<second[0]<<endl;
  65.             time+=second[0];
  66.             output<<second[0]<<" "<<first[0]<<endl;
  67.             time+=first[0];
  68.             second.push_back(first[0]);
  69.  
  70.         }
  71.         else 
  72.         {
  73.             bool test1=(first[1]+first[0]+first[first.size()-2]+first[1])<(first[0]+first[0]+first[first.size()-1]+first[first.size()-2]);
  74.            if(test1)
  75.            {
  76.                 //first 2
  77.                 output<<first[0]<<" "<<first[1]<<endl;
  78.                 time+=first[1];
  79.                 second.push_back(first[0]);
  80.                 second.push_back(first[1]);
  81.                 first.pop_front();
  82.                 first.pop_front();
  83.                 sort(second.begin(),second.end());
  84.                 first.push_front(second[0]);
  85.                 output<<second[0]<<endl;
  86.                 time+=second[0];
  87.                 second.pop_front();
  88.  
  89.                 //last 2
  90.                 output<<first[first.size()-2]<<" "<<first[first.size()-1]<<endl;
  91.                 time+=first[first.size()-1];
  92.                 second.push_back(first[first.size()-2]);
  93.                 second.push_back(first[first.size()-1]);
  94.                 first.pop_back();
  95.                 first.pop_back();
  96.  
  97.                 first.push_front(second.front());
  98.                 time+=first.front();
  99.                 output<<first.front()<<endl;
  100.                 second.pop_front();
  101.            }
  102.  
  103.            else
  104.            {
  105.                 //first 2
  106.                 output<<first[0]<<" "<<first[first.size()-1]<<endl;
  107.                 time+=first[first.size()-1];
  108.                 second.push_back(first[0]);
  109.                 second.push_back(first[first.size()-1]);
  110.                 first.pop_front();
  111.                 first.pop_back();
  112.                 sort(second.begin(),second.end());
  113.                 first.push_front(second[0]);
  114.                 output<<second[0]<<endl;
  115.                 time+=second[0];
  116.                 second.pop_front();
  117.  
  118.  
  119.                 //last 2
  120.                 output<<first[0]<<" "<<first[first.size()-1]<<endl;
  121.                 time+=first[first.size()-1];
  122.                 second.push_back(first[0]);
  123.                 second.push_back(first[first.size()-1]);
  124.                 first.pop_back();
  125.                 first.pop_front();
  126.                 sort(second.begin(),second.end());
  127.                 first.push_front(second.front());
  128.                 time+=first.front();
  129.                 output<<first.front()<<endl;
  130.                 second.pop_front();
  131.            }
  132.  
  133.         }
  134.     }
  135.  
  136.     cout<<time<<endl;
  137.     cout<<output.str();
  138. }
  139.  
  140. int main() {
  141.  
  142.     int num_cases,n,temp;
  143.     string line;
  144.     cin>>num_cases;
  145.     getline(cin,line);
  146.  
  147.     for(int i=0;i<num_cases;i++)
  148.     {
  149.        getline(cin,line);
  150.        cin>>n;
  151.        cin.ignore();
  152.        deque<int> speeds;
  153.  
  154.        for(int j=0;j<n;j++)
  155.        {
  156.            cin>>temp;
  157.            cin.ignore();
  158.            speeds.push_back(temp);
  159.        }
  160.        cross(speeds);
  161.  
  162.        if(i<num_cases-1)
  163.        {
  164.            cout<<endl;
  165.        }
  166.     }
  167.     return 0;
  168.  
  169. }
  170.  
Success #stdin #stdout 0s 3460KB
comments (?)
stdin
copy 
2

1
1

2
10
10
stdout
copy 
1
1

10
10 10
https://ideone.com/ST8lEr
language:
C++ (gcc 8.3)
created:
10 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!