(23435) Cloud computing

https://www.acmicpc.net/problem/23435

단계별로 풀어보기

41단계(인터랙티브와 투 스텝 1) 9번째

 

 

 

배열의 요소를 두 개씩 비교해서 나온 결과만으로 두 번째로 큰 요소를 찾아야 한다.

토너먼트 방식으로 요소를 비교해 가장 큰 요소를 찾아냈다고 하자. 이때 두 번째로 큰 요소는 이 요소 빼고 다른 요소보다 크므로, 계속 선택받다가 가장 큰 요소와 비교했을 때 떨어졌을 것이다.

따라서 가장 큰 요소와 비교했던 요소들을 기록한 뒤(물론 무엇이 가장 큰 요소인지 모르므로 모든 비교 결과를 기록해둬야 한다) 그 요소들만 가지고 다시 가장 큰 요소를 찾아내면 된다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;

int main() 
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  char resp;
  
  int n;
  cin >> n;
  
  vector<int> v(n);
  vector<int> v2;
  vector record(n, vector<int> ());
  
  for(int i=0;i<n;i++)  v[i]= i;
  
  while(v.size()>1){
    for(int i=0 ; i<v.size() ; i+=2){
      if(i+1==v.size()){
        v2.push_back(v[i]);
        break;
      }
      
      cout << "? " << v[i] << " " << v[i+1] << endl;
      cin >> resp;
      
      if(resp=='<'){
        v2.push_back(v[i]);
        record[v[i]].push_back(v[i+1]);
      }else{
        v2.push_back(v[i+1]);
        record[v[i+1]].push_back(v[i]);
      }
    }
    
    v= v2;
    v2= vector<int> ();
  }
  
  v= record[v[0]];
  v2= vector<int> ();
  
  while(v.size()>1){
    for(int i=0 ; i<v.size() ; i+=2){
      if(i+1==v.size()){
        v2.push_back(v[i]);
        break;
      }
      
      cout << "? " << v[i] << " " << v[i+1] << endl;
      cin >> resp;
      
      if(resp=='<'){
        v2.push_back(v[i]);
      }else{
        v2.push_back(v[i+1]);
      }
    }
    
    v= v2;
    v2= vector<int> ();
  }
  
  cout << "! " << v[0];
  
  return 0;
}