A. Аккаунты

Codeforces

IDCF10155A

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Проникнув на базу группировки «Золотое кольцо», Эггси и его бывший наставник Гарри вскоре получили доступ к ноутбуку Поппи Адамс. Теперь им необходимо вычислить, отыскать, а впоследствии и арестовать всех участников «Золотого кольца». В процессе долгих поисков агенты наткнулись на нужный им документ — список логинов и паролей всех сотрудников, с помощью которых можно войти в их аккаунты во внутренней системе группировки и узнать имя и местоположение каждого преступника. Но Поппи оказалась очень умна и поэтому перемешала все логины и пароли в списке так, что на первый взгляд он представлен в виде списка случайных строк. Однако ребята из «Кингсман» не менее сообразительны и быстро догадались, как сопоставить две строки из списка так, чтобы одна из них оказалась логином, а вторая — подходящим паролем. Логин представляет из себя строку, состоящую из строчных латинских букв. Корректный пароль к нему представляет собой логин с приписанными к нему справа какими-либо маленькими латинскими буквами (возможно, количество приписанных букв нулевое). То есть логин является префиксом подходящего ему пароля. Ваша задача — отыскать соответствующие друг другу логины и пароли. Каждая строка из списка может быть использована в качестве логина или пароля ровно один раз. В первой строке входного файла находится натуральное число n — количество аккаунтов (1 ≤ n ≤ 105). В следующих 2 × n строках дано по одной строке, состоящей из строчных латинских букв. Суммарная длина строк не превышает 5 × 105. В выходной файл выведите n строк, в каждой из которых два числа — первое из которых является индексом строки логина, а второе — индексом строки пароля. Гарантируется, что ответ существует. Если ответов несколько, выведите любой. ## Входные Данные В первой строке входного файла находится натуральное число n — количество аккаунтов (1 ≤ n ≤ 105).В следующих 2 × n строках дано по одной строке, состоящей из строчных латинских букв. Суммарная длина строк не превышает 5 × 105. ## Выходные Данные В выходной файл выведите n строк, в каждой из которых два числа — первое из которых является индексом строки логина, а второе — индексом строки пароля.Гарантируется, что ответ существует. Если ответов несколько, выведите любой. ## Пример Входные данные2abacabacababaabaaВыходные данные3 41 2 [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of accounts. Let $ S = (s_1, s_2, \dots, s_{2n}) $ be a sequence of $ 2n $ strings over lowercase Latin letters. **Constraints** 1. $ 1 \leq n \leq 10^5 $ 2. $ \sum_{i=1}^{2n} |s_i| \leq 5 \times 10^5 $ 3. Each string $ s_i $ consists only of lowercase Latin letters. 4. There exists a perfect matching between $ n $ login-password pairs such that for each pair $ (s_i, s_j) $, $ s_i $ is a prefix of $ s_j $, and each string is used exactly once. **Objective** Find a bijection $ M \subseteq \{1, \dots, 2n\} \times \{1, \dots, 2n\} $ such that: - $ |M| = n $, - For each $ (i, j) \in M $, $ s_i $ is a prefix of $ s_j $, - Each index appears in exactly one pair, - Output the set $ M $ as $ n $ pairs $ (i, j) $, where $ i $ is the index of the login and $ j $ is the index of the password.

API Response (JSON)

{
  "problem": {
    "name": "A. Аккаунты",
    "description": {
      "content": "Проникнув на базу группировки «Золотое кольцо», Эггси и его бывший наставник Гарри вскоре получили доступ к ноутбуку Поппи Адамс. Теперь им необходимо вычислить, отыскать, а впоследствии и арестовать ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10155A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Проникнув на базу группировки «Золотое кольцо», Эггси и его бывший наставник Гарри вскоре получили доступ к ноутбуку Поппи Адамс. Теперь им необходимо вычислить, отыскать, а впоследствии и арестовать ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of accounts.  \nLet $ S = (s_1, s_2, \\dots, s_{2n}) $ be a sequence of $ 2n $ strings over lowercase Latin letters.  \n\n**Constraints**  \n1. $ ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments