# 14228: 【原4228】email

### 题目描述

author: Shuhao Li 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4228

## Sample Input

5
alice [email protected]
bob [email protected]
alicebest [email protected]
bob2 [email protected]
alice2016 [email protected]

## Sample Output

alice alicebest alice2016
bob bob2

## BugenZhao's solution

//
// Created by BugenZhao on 2019/4/29.
//

#include <iostream>
#include <string>

using std::ios, std::cin, std::cout, std::endl, std::string;
using ll = long long;

#ifndef SBL_BBINARYSEARCHTREE_H
#define SBL_BBINARYSEARCHTREE_H

template<typename Key, typename Val>
class BPair {
public:
Key key;
Val val;

BPair(Key key, Val val) : key(key), val(val) {}

BPair() = delete;
};

template<typename Key, typename Val>
class BBinarySearchTree {
class Node {
public:
BPair<Key, Val> data;
Node *left;
Node *right;

explicit Node(const BPair<Key, Val> &data, Node *left = nullptr, Node *right = nullptr) :
data(data), left(left), right(right) {}
};

Node *root;
int size;

private:
BPair<Key, Val> *get(Node *node, const Key &key) {
if (node == nullptr || node->data.key == key)
return &node->data;
if (key < node->data.key)
return get(node->left, key);
else
return get(node->right, key);
}

void put(Node *&node, const Key &key, const Val &val) {
if (node == nullptr)
node = new Node({key, val});
else if (key < node->data.key)
put(node->left, key, val);
else if (key > node->data.key)
put(node->right, key, val);
else
node->data.val = val;
}

void remove(Node *&node, const Key &key) {
if (node == nullptr)
return;
if (key < node->data.key)
remove(node->left, key);
else if (key > node->data.key)
remove(node->right, key);
else if (node->right == nullptr) {
auto oldNode = node;
node = node->left;
delete oldNode;
} else if (node->left == nullptr) {
auto oldNode = node;
node = node->right;
delete oldNode;
} else {
auto p = node->right;
while (p->left != nullptr) p = p->left;
node->data = p->data;
remove(node->right, node->data.key);
}
}

void clear(Node *&node) {
if (node == nullptr) return;
clear(node->left);
clear(node->right);
delete node;
--size;
}

public:
BBinarySearchTree() : root(nullptr), size(0) {}

BPair<Key, Val> *get(const Key &key) {
return get(root, key);
}

void put(const Key &key, const Val &val) {
put(root, key, val);
}

void remove(const Key &key) {
remove(root, key);
}

void clear() {
clear(root);
}

virtual ~BBinarySearchTree() {
clear();
}
};

#endif //SBL_BBINARYSEARCHTREE_H

#include <stdexcept>

template<typename Item>
class Node {
public:
Item item;
Node *next;

explicit Node(const Item &item, Node *next = nullptr) : item(item), next(next) {}

explicit Node(Node *next = nullptr) : next(next) {}

virtual ~Node() = default;
};

int N;
Node *tail;

Node *getNode(int i) {
while (i--) {
ret = ret->next;
}
return ret;
}

public:
N = 0;
}

N = 0;
}
}

void clear() {
Node *tmp;
while (p) {
tmp = p;
p = p->next;
delete tmp;
}
N = 0;
}

clear();
}

int size() const {
return N;
}

auto node = new Node(item);
tail->next = node;
tail = node;
++N;
}

auto node = new Node(item, tmp);
++N;
}

void insert(int i, const Item &item) {
if (i == 0)
else if (i == N)
else if (i >= N || i < 0)
else {
auto p = getNode(i - 1);
auto tmp = p->next;
auto node = new Node(item, tmp);
p->next = node;
++N;
}
}

const Item &get(int i) {
if (i >= N || i < 0)
return getNode(i)->item;
}

void set(int i, const Item &item) {
if (i >= N || i < 0)
getNode(i)->item = item;
}

private:
class Iterator {
Node *it;
Node *tail;
public:

bool hasNext() const {
return it != tail;
}

Item &next() {
return (it = it->next)->item;
}

const Item &next() const {
return (it = it->next)->item;
}
};

public:
Iterator iterator() const {
}

friend int main();
};

int count = 0;

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;

string name, email;

while (N--) {
cin >> name >> email;
auto p = bst.get(email);
else {
auto list = lists[count++];
bst.put(email, list);
}
}

auto it = emails.iterator();
while (it.hasNext()) {
auto itt = bst.get(it.next())->val->iterator();
while (itt.hasNext()) {
cout << itt.next() << ' ';
}
cout << '\n';
}

auto p = lists;
while (*p) {
delete p;
p += 1;
}
return 0;
}

## skyzh's solution

#include <iostream>
#include <cstring>

using namespace std;

class NotFoundError {
};

class DuplicateKeyError {
};

struct String {
const char *str;

String(const char *str) : str(str) {}

friend int cmp(const String &a, const String &b) {
return strcmp(a.str, b.str);
}
};

int cmp(int a, int b) {
if (a < b) return -1;
if (a == b) return 0;
if (a > b) return 1;
}

template<typename T>
struct Vector {
static const int VEC_DEF_SIZE = 16;
int cap;
int siz;
T *data;

Vector(T x) : cap(VEC_DEF_SIZE), siz(1), data(new T[cap]) { data[0] = x; }

Vector() : cap(VEC_DEF_SIZE), siz(0), data(new T[cap]) {}

void expand() {
T *buffer = new T[cap * 2];
memcpy(buffer, data, sizeof(T) * cap);
cap *= 2;
delete[] data;
data = buffer;
}

void append(T x) {
if (siz == cap) expand();
data[siz++] = x;
}
};

template<typename Key, typename T>
struct LLRB {
struct Node {
Key key;
T x;
Node *l, *r;
bool is_red;

Node(const Key &key, const T &x, Node *l = nullptr, Node *r = nullptr) : key(key), x(x), l(l), r(r),
is_red(true) {}

friend bool is_red(const Node *ptr) {
return ptr && ptr->is_red;
}

friend Node *rotate_left(Node *h) {
Node *r = h->r;
// assert(r->is_red);
h->r = r->l;
r->l = h;
r->is_red = h->is_red;
h->is_red = true;
return r;
}

friend Node *rotate_right(Node *h) {
Node *l = h->l;
// assert(l->is_red);
h->l = l->r;
l->r = h;
l->is_red = h->is_red;
h->is_red = true;
return l;
}

friend void flip_colors(Node *h) {
// assert(!h->is_red);
// assert(h->l->is_red);
// assert(h->r->is_red);
h->is_red = true;
h->l->is_red = h->r->is_red = false;
}
} *root;

LLRB() : root(nullptr) {}

Node *find(const Key &key, Node *ptr) {
if (!ptr) return nullptr;
int _ = cmp(key, ptr->key);
if (_ < 0) return find(key, ptr->l);
if (_ > 0) return find(key, ptr->r);
return ptr;
}

T &find(const Key &key) {
return find(key, root)->x;
}

Node *exist(const Key &key) {
return find(key, root);
}

Node *insert(const Key &key, const T &x, Node *ptr) {
if (!ptr) return new Node(key, x);
int _ = cmp(key, ptr->key);
if (_ < 0) ptr->l = insert(key, x, ptr->l);
if (_ > 0) ptr->r = insert(key, x, ptr->r);
if (_ == 0) throw DuplicateKeyError();

if (!is_red(ptr->l) && is_red(ptr->r)) ptr = rotate_left(ptr);
if (is_red(ptr->l) && is_red(ptr->l->l)) ptr = rotate_right(ptr);
if (is_red(ptr->l) && is_red(ptr->r)) flip_colors(ptr);

return ptr;
}

void insert(const Key &key, const T &x) {
root = insert(key, x, root);
}

template<typename U>
void traverse(U *func, Node *ptr) {
if (!ptr) return;
traverse(func, ptr->l);
func(ptr);
traverse(func, ptr->r);
}

template<typename U>
void traverse(U *func) {
traverse(func, root);
}
};

LLRB<String, Vector<const char *>> llrb;
LLRB<int, String> cnt;

void print(LLRB<int, String>::Node *ptr) {
auto rec = llrb.find(ptr->x);
for (int i = 0; i < rec.siz; i++) printf("%s ", rec.data[i]);
printf("\n");
return;
}

int main() {
int N;

scanf("%d", &N);
for (int i = 0; i < N; i++) {
char *name = new char[1024], *email = new char[1024];
scanf("%s%s", name, email);
auto *ptr = llrb.exist(String(email));
if (!ptr) {
llrb.insert(String(email), Vector<const char *>(name));
cnt.insert(i, String(email));
} else {
ptr->x.append(name);
}
}

cnt.traverse(print);

return 0;
}