fork download 
  1. //tonynater - COCI 2014-2015
  2.  
  3. #include <algorithm>
  4. #include <iostream>
  5. #include <vector>
  6.  
  7. #define sz(x) ((int) x.size())
  8.  
  9. using namespace std;
  10.  
  11. typedef long long ll;
  12.  
  13. const ll INF = ll(1)<<60;
  14.  
  15. const int MAXN = 100010;
  16.  
  17. int N, A[MAXN];
  18.  
  19. vector<int> F, V;
  20.  
  21. int main() {
  22.     ios_base::sync_with_stdio(0);
  23.     cin.tie(NULL);
  24.  
  25.     cin >> N;
  26.  
  27.     for(int i = 0; i < N; i++) {
  28.         cin >> A[i];
  29.     }
  30.  
  31.     sort(A, A+N);
  32.  
  33.     for(int i = 0; i < N;) {
  34.         int b = i, e = i;
  35.         while(e < N && A[b] == A[e]) {
  36.             ++e;
  37.         }
  38.         F.push_back(e-b);
  39.         V.push_back(A[b]);
  40.         i = e;
  41.     }
  42.  
  43.     int lb, rb;
  44.     ll low = 0, high = INF;
  45.     while(low < high) {
  46.         ll mid = (low+high)/2;
  47.  
  48.         lb = 0;
  49.         ll sum = 0, cur = 0;
  50.         for(; lb < sz(F)-1; lb++) {
  51.             cur += F[lb];
  52.             sum += cur;
  53.             if(sum == (mid+1)/2) {
  54.                 ++lb;
  55.                 break;
  56.             }else if(sum > (mid+1)/2){
  57.                 break;
  58.             }
  59.         }
  60.  
  61.         rb = sz(F)-1;
  62.         sum = 0, cur = 0;
  63.         for(; rb > 0; rb--) {
  64.             cur += F[rb];
  65.             sum += cur;
  66.             if(sum == mid/2) {
  67.                 --rb;
  68.                 break;
  69.             }else if(sum > mid/2) {
  70.                 break;
  71.             }
  72.         }
  73.  
  74.         if(rb-lb > 1) {
  75.             low = mid+1;
  76.         }else {
  77.             high = mid;
  78.         }
  79.     }
  80.  
  81.     lb = 0;
  82.     ll sum = 0, cur = 0;
  83.     for(; lb < sz(F)-1; lb++) {
  84.         cur += F[lb];
  85.         sum += cur;
  86.         if(sum == (low+1)/2) {
  87.             ++lb;
  88.             break;
  89.         }else if(sum > (low+1)/2){
  90.             break;
  91.         }
  92.     }
  93.  
  94.     rb = sz(F)-1;
  95.     sum = 0, cur = 0;
  96.     for(; rb > 0; rb--) {
  97.         cur += F[rb];
  98.         sum += cur;
  99.         if(sum == low/2) {
  100.             --rb;
  101.             break;
  102.         }else if(sum > low/2) {
  103.             break;
  104.         }
  105.     }
  106.  
  107.     if(low%2 == 0) {
  108.         cout << "Slavko\n" << V[lb] << ' ' << V[rb] << '\n';
  109.     }else {
  110.         cout << "Mirko\n" << V[lb] << ' ' << V[rb] << '\n';
  111.     }
  112.  
  113.     return 0;
  114. }
Success #stdin #stdout 0s 3868KB
comments (?)
stdin 
7
2 1 3 3 5 4 1
stdout 
Slavko
2 3
https://ideone.com/nmp1PH
language:
C++14 (gcc 8.3)
created:
10 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!