Yandex.Algorithm 2014 Qualification round A問題 - The Last Dart

Source

Yandex.Algorithm 2014
Yandex.Algorithm 2014 Qualification round
問題文

問題概要

$N = 2^K$ チームで負けたら即敗退のトーナメント戦を行う.合計で $K$ 回戦で引き分けはない.
全 $N-1$ 試合の勝者と敗者のチーム名が,順不同で与えられるので,優勝チーム名を出力する問題.

解法

勝ったことのあるチーム名,負けたことのあるチーム名を全てセットやハッシュにつっこみ,勝ったことはあるけど,負けたことのないチームを探す.

C++によるスパゲッティなソースコード

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}c[s]='\0';return s;}
void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);}

set<string> win, lose;
set<string>::iterator it;

int main(){
  int N;
  int i, j, k;
  char buf[100];

  reader(&N);
  REP(i,1,N){
    reader(buf);
    win.insert(buf);
    reader(buf);
    lose.insert(buf);
  }

  for(it = win.begin(); it != win.end(); it++){
    if(lose.count(*it)==0){
      writer(it->c_str());
      writer("\n");
      break;
    }
  }

  return 0;
}

Current time: 2024年03月19日17時11分53秒
Last modified: 2014年06月25日20時25分49秒 (by laycrs)
Tags: Competitive_Programming Yandex_Algorithm Yandex_Algorithm_2014 Yandex_Algorithm_2014_Qual
トップページに戻る

Logged in as: unknown user (not login)

ログイン: