#include #include #include #include #include using namespace std; int main() { typedef multimap> intmap; intmap mmp; mmp.insert(intmap::value_type(1000000000, 1)); int rs; cin >> rs; stringstream res; for (int i = 0 ;i < rs ;++i) { int id, sorce; cin >> id >> sorce; if (mmp.size() == 1) { res << id << " " << 1 << endl; mmp.insert(make_pair(sorce, id)); for (intmap::iterator ii = mmp.begin(); ii != mmp.end();++ii) { cout << "(" << ii->first << "," << ii->second << ")"; } cout << endl; } else { intmap::iterator pp = mmp.insert(make_pair(sorce, id)); for (intmap::iterator ii = mmp.begin(); ii != mmp.end();++ii) { cout << "(" << ii->first << "," << ii->second << ")"; } cout << endl; intmap::iterator aa(pp); intmap::iterator bb(pp); if (aa == mmp.begin()) { int iid = (++aa)->second; int isorce = aa->first; while (mmp.end() != (++aa) && isorce == aa->first) { if (aa->second < iid) { iid = aa->second; isorce == aa->first; } } res << id << " " << iid << endl; } else { int xid = (--bb)->second; int xsorce = bb->first; int did = (++aa)->second; int dsorce = aa->first; if ((sorce - xsorce) < (dsorce - sorce)) { res << id << " " << xid << endl; } else if((sorce - xsorce) > (dsorce - sorce)) { res << id << " " << did << endl; } else { //cout << (mmp.begin() == (bb)) << endl; while (mmp.begin() != bb && (xsorce == bb->first)) { if (bb->second < xid) { xid = bb->second; xsorce = bb->first; } --bb; } while ( mmp.end() != aa && (dsorce == aa->first)) { if (aa->second < did) { did = aa->second; dsorce = aa->first; } ++aa; } if (xid < did) { res << id << " " << xid << endl; } else { res << id << " " << did << endl; } } } } } cout << res.str(); for (intmap::iterator ii = mmp.begin(); ii != mmp.end();++ii) { cout << "(" << ii->first << "," << ii->second << ")"; } return 0; }