Problem:


Score : 700 points

Problem Statement

You are given a string s of length n.
Does a tree with n vertices that satisfies the following conditions exist?

The vertices are numbered 1,2,..., n.

The edges are numbered 1,2,..., n-1, and Edge i connects Vertex u_i and v_i.

If the i-th character in s is 1, we can have a connected component of size i by removing one edge from the tree.

If the i-th character in s is 0, we cannot have a connected component of size i by removing any one edge from the tree.

If such a tree exists, construct one such tree.

Constraints

2 \leq n \leq 10^5

s is a string of length n consisting of 0 and 1.

Input

Input is given from Standard Input in the following format:

s

Output

If a tree with n vertices that satisfies the conditions does not exist, print -1.

If a tree with n vertices that satisfies the conditions exist, print n-1 lines.
The i-th line should contain u_i and v_i with a space in between.
If there are multiple trees that satisfy the conditions, any such tree will be accepted.

Sample Input 1

1111

Sample Output 1

-1

It is impossible to have a connected component of size n after removing one edge from a tree with n vertices.

Sample Input 2

1110

Sample Output 2

1 2
2 3
3 4

If Edge 1 or Edge 3 is removed, we will have a connected component of size 1 and another of size 3. If Edge 2 is removed, we will have two connected components, each of size 2.

Sample Input 3

1010

Sample Output 3

1 2
1 3
1 4

Removing any edge will result in a connected component of size 1 and another of size 3.



Sample input:
1111


Sample output:
-1

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(S):
    N = len(S)
    if S[N-1] == '1':
        print(-1)
        return -1

    if S[0] != '1':
        print(-1)
        return -1

    if S[N-2] != '1':
        print(-1)
        return -1


    for i in range(N//2):
        if S[i] != S[N-2-i]:
            print(-1)
            return -1

    comp = []
    g = defaultdict(set)

    l = [1]
    r = [j for j in range(2, N+1)]
    u = l.pop()
    v = r.pop()
    g[u].add(v)
    g[v].add(u)
    heapq.heappush(comp, (len(l), (u, l)))
    heapq.heappush(comp, (len(r), (v, r)))
    for i in range(2, N//2+1):
        if S[i-1] == '0':
            continue
        else:
            c = 0
            while c < i:
                c, (u, chs) = heapq.heappop(comp)
                if c < i:
                    for v in chs:
                        g[u].add(v)
                        g[v].add(u)

            l = chs[:i]
            v = l.pop()
            g[u].add(v)
            g[v].add(u)
            heapq.heappush(comp, (len(l), (v, l)))

            r = chs[i:]
            for v in r:
                g[u].add(v)
                g[v].add(u)
    while comp:
        _, (u, vs) = comp.pop()
        for v in vs:
            g[u].add(v)
            g[v].add(u)

    for i in range(1, N+1):
        for j in range(i+1, N+1):
            if j in g[i]:
                print(i, j)


def main():
    S = read_str()
    (slv(S))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(S):
    N = len(S)
    if S[N-1] == '1':
        return -1

    if S[0] != '1':
        return -1

    if S[N-2] != '1':
        return -1


    for i in range(N//2):
        if S[i] != S[N-2-i]:
            return -1

    comp = []
    g = defaultdict(set)

    l = [1]
    r = [j for j in range(2, N+1)]
    u = l.pop()
    v = r.pop()
    g[u].add(v)
    g[v].add(u)
    heapq.heappush(comp, (len(l), (u, l)))
    heapq.heappush(comp, (len(r), (v, r)))
    for i in range(2, N//2+1):
        if S[i-1] == '0':
            continue
        else:
            c = 0
            while c < i:
                c, (u, chs) = heapq.heappop(comp)
                if c < i:
                    for v in chs:
                        g[u].add(v)
                        g[v].add(u)

            l = chs[:i]
            v = l.pop()
            g[u].add(v)
            g[v].add(u)
            heapq.heappush(comp, (len(l), (v, l)))

            r = chs[i:]
            for v in r:
                g[u].add(v)
                g[v].add(u)
    while comp:
        _, (u, vs) = comp.pop()
        for v in vs:
            g[u].add(v)
            g[v].add(u)

    for i in range(1, N+1):
        for j in range(i+1, N+1):
            if j in g[i]:
                print(i, j)


def main():
    S = read_str()
    (slv(S))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import itertools
S = input()
N = len(S)
S = '0' + S
A = [[int(i), len(list(v))] for i, v in itertools.groupby(S)]
if A[0][0] == A[-1][0] == 0 and A[1][0] == A[-2][0] == A[0][1] == A[-1][1] == 1:
    if len(A) == 3:
        #一直線
        for i in range(1, N):
            print(i, i + 1)
        exit()
    elif len(A) == 5 and A[1][1] == A[-2][1]:
        #脚の長さの最大値がA[1][1]のstar graph
        M = A[1][1]
        Q, R = N // M, N % M
        #Q本の長さMの脚、1本の長さRの脚
        a = [[N] for _ in range(Q + 1)]
        for i in range(1, N):
            a[i % (Q + 1)] += [i]
        for b in a:
            for c, d in zip(b, b[1:]):
                print(c, d)
        exit()
print(-1)

Submission status: Runtime Error

Solution code:
import itertools
S = input()
N = len(S)
S = '0' + S
A = [[int(i), len(list(v))] for i, v in itertools.groupby(S)]
if A[0][0] == A[-1][0] == 0 and A[1][0] == A[-2][0] == A[0][1] == A[-1][1] == 1:
    if len(A) == 3:
        #一直線
        for i in range(1, N):
            print(i, i + 1)
        exit()
    elif len(A) == 5 and A[1][1] == A[-2][1]:
        #脚の長さの最大値がA[1][1]+1のstar graph
        M = A[1][1] + 1
        Q, R = N // M, N % M
        #Q本の長さMの脚、1本の長さRの脚
        a = [[N] for _ in range(Q + 1)]
        for i in range(1, N):
            a[i % (Q + 1)] += [i]
        for b in a:
            for c, d in zip(b, b[1:]):
                print(c, d)
        exit()
print(-1)

Submission status: Runtime Error

Solution code:
import math

s = input()

N = len(s)
s = "#" + s
possible = 1
if s[-1] == "1" or s[1] == "0":
  possible = 0
for i in range(1,math.floor(N/2)):
  if s[i] != s[N - i]:
    possible = 0

if not possible:
  print(-1)
elif N == 2:
  if s[1] == "1" and s[2] == "0":
    print(1, 2)
  else:
    print(-1)
elif N == 3:
  if s[1] == "1" and s[2] == "1":
    print(1,2)
    print(2,3)
  else:
    print(-1)
else:
  destination_1sthalf = [1] * (math.floor(N/2) + 2)
  destination_2ndhalf = [1] * (N - math.floor(N/2) -1)
  root = 2
  max_bit = math.floor(N/2)
  for i in range(max_bit, -1, -1):
    if s[i] == "1":
      destination_1sthalf = destination_1sthalf[:root+1] + [root]*(i-1)
      root += 1
  destination = destination_1sthalf + destination_2ndhalf
  for i in range(2,N+1):
    print(i, destination[i])

Submission status: Runtime Error

Solution code:
import math

s = input()

N = len(s)
s = "#" + s
possible = 1
if s[-1] == "1":
  possible = 0
for i in range(1,math.floor(N/2)):
  if s[i] != s[N - i]:
    possible = 0

if not possible:
  print(-1)
else:
  destination = [1] * (N+1)
  root = 2
  for i in range(math.floor(N/2), -1, -1):
    if s[i] == "1":
      for j in range(1, i):
        destination[root + j] = root
      root += 1
for i in range(2,N+1):
  print(i, destination[i])

Submission status: Runtime Error

Solution code:
s = input()
n = len(s)

if s[0] == '0' or s[-1] == '1':
    print(-1)
    exit()
for i in range(n-1):
    if s[i] != s[-2-i]:
        print(-1)
        exit()

ans = [(1, v) for v in range(2, n+1)]
u_child = 2
i_replace = -1
for i in range(1, n//2):
    if s[i] == '1':
        for _ in range(i):
            ans[i_replace] = (u_child, ans[i_replace][1])
            i_replace -= 1
        u_child += 1
for a in ans:
    print(*a)

Submission status: Runtime Error

Solution code:
input()
print(input().split().index('1')+1)

Submission status: Runtime Error

Solution code:
S = input()
N = len(S)

if S[-1] == "1":
    print(-1)
    exit()

S2 = S[:-1]
for i in range((N - 1) // 2):
    if S2[i] != S2[N - i - 1]:
        print(-1)
        exit()

# 構築
T = [[] for i in range(N)]

next = 1
mark = 0
for i in range(N):
    child = mark + 1
    if S[i] == "0":
        next += 1
    else:
        for n in range(next):
            T[mark].append(child)
            child += 1
        next = 1
        mark = child - 1

for i in range(N):
    for t in T[i]:
        print(i+1, t+1)

Submission status: Runtime Error

Solution code:
S = input()
N = len(S)

if S[-1] == "1":
    print(-1)
    exit()

S2 = S[:-1]
for i in range(N // 2 + 1):
    if S2[i] != S2[N - i - 1]:
        print(-1)
        exit()

# 構築
T = [[] for i in range(N)]

next = 1
mark = 0
for i in range(N):
    child = mark + 1
    if S[i] == "0":
        next += 1
    else:
        for n in range(next):
            T[mark].append(child)
            child += 1
        next = 1
        mark = child - 1

for i in range(N):
    for t in T[i]:
        print(i+1, t+1)

Submission status: Runtime Error

Solution code:
s = input()

def print_index(x,y):
    if y > len(s):
        return
    print(x,y)

def solve(s,index):
    if not s:
        return
    if s[0]=="1":
        print_index(index,index+1)
        return solve(s[1:],index+1)
    else:
        print_index(index,index+1)
        print_index(index,index+2)
        return solve(s[1:],index+1)


(solve(s,1))

Submission status: Runtime Error

Solution code:
S = input()
N = len(S)

if S[-1] == "1":
    print(-1)
    exit()

R = []
for i in range(N // 2):
    if S[i] == "1":
        if S[N - i - 2] == "1":
            R.append(i + 1)
        else:
            print(-1)
            exit()

# 構築
T = [[] for i in range(N)]

next = 1
mark = 0
for i in range(N):
    child = mark + 1
    if S[i] == "0":
        next += 1
    else:
        for n in range(next):
            T[mark].append(child)
            child += 1

        mark = child - 1

for i in range(N):
    for t in T[i]:
        print(i+1, t+1)

Submission status: Runtime Error

Solution code:
S = input()
N = len(S)

if S[-1] == "1":
    print(-1)
    exit()

R = []
for i in range(N // 2):
    if S[i] == "1":
        if S[N - i - 2] == "1":
            R.append(i + 1)
        else:
            print(-1)
            exit()

R_max = max(R)
for s in S[1:R_max-1]:
    if s == "0":
        print(-1)
        exit()


# 構築
T = [[] for i in range(N + 1)]

# R_maxの数だけ伸ばす
for i in range(1, R_max + 1):
    T[i].append(i + 1)

# 他はすべて1につなぐ
for i in range((R_max + 2), N + 1):
    T[1].append(i)

for i in range(1, N+1):
    for t in T[i]:
        print(i, t)