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: Wrong Answer

Solution code:
S = input()
eda = []
flag = False
N = len(S)
if S[-1] == '1':
  flag = True
if S[0] == '0':
  flag = True
if S[-2] == '0':
  flag = True
for k in range((N-1)//2):
  if S[k] != S[-k-2]:
    flag = True
  if S[k] == '1':
    eda.append(k+1)
if N%2 == 0:
  if S[N//2 -1] == '1':
    eda.append(N//2)
if flag:
  print(-1)
  exit()
ans = []
before = eda.pop()
while eda:
  after = eda.pop()
  for k in range(before, after):
    ans.append((k, after))
  before = after
ans.append((before, before+1))
for k in range(before+2, N+1):
  ans.append((before+1, k))
while ans:
  item = ans.pop()
  print(item[0], item[1])

Submission status: Wrong Answer

Solution code:
s = input()
if(s[0]=='0')|(s[-1]=='1'):
    print(-1)
    exit()

n = len(s)
size = []
for i in range(1,n//2):
    sl = s[i]
    sr = s[n-2-i]
    if(sl != sr):
        print(-1)
        exit()
    if(sl=='1'):
        size.append(i+1)

size.append(n)
ans = []
now = 1
for si in size:
    for j in range(now+1,si+1):
        ans.append(' '.join(map(str,[now,j])))
    now = si

print('\n'.join(ans))

Submission status: Wrong Answer

Solution code:
def examC():
    N = I()
    A = LI()
    d0 = defaultdict(int); d0[0] = 0
    d1 = defaultdict(int); d1[0] = 0
    for i in range(N):
        if i%2==0:
            d0[A[i]] +=1
        else:
            d1[A[i]] +=1
    n0 = sorted(d0.items(),key=lambda x:x[1])
    n1 = sorted(d1.items(),key=lambda x:x[1])
#    print(n0); print(n1)
    if n0[-1][0]!=n1[-1][0]:
        ans = N - n0[-1][1] - n1[-1][1]
    else:
        ans = N - max(n0[-1][1]+n1[-2][1],n0[-2][1]+n1[-1][1])
    print(ans)
    return

def examE():
    S = SI(); N = len(S)
    if S[-1]=="1" or S[0]=="0":
        print(-1)
        return
    flag = [False]*(N//2)
    for i in range(N//2):
        if S[i]!=S[N-i-2]:
            print(-1)
            return
        if S[i]=="1":
            flag[i] = True
    print(flag)
    ans = [[] for _ in range(N-1)]
    now = 0; cur = 0
    for i in range(N-1):
        print(ans)
        if i>=(N//2):
            if cur>N-1:
                continue
            ans[cur] = [now,cur]
            cur +=1
            continue
        if flag[i]:
            ans[cur] = [i+1,i+2]
            now = i+2
            cur +=1
        else:
            for k in range(i):
                ans[cur] = [i+1, i + 2+k]
                now = i+1
                cur +=1
    for v in ans:
        print(" ".join(map(str,v)))
    return

def examE2():
    S = SI(); N = len(S)
    if S[-1]=="1" or S[0]=="0":
        print(-1)
        return
    for i in range(N//2):
        if S[i]!=S[N-i-2]:
            print(-1)
            return
    dep = -1
    for i in range(N//2):
        if S[i]!=S[N-i-2]:
            print(-1)
            return
        if S[i]=="1":
            if dep!=-1:
                print(-1)
                return
        else:
            if dep==-1:
                dep = i
    ans = [[] for _ in range(N-1)]
    cnt = 0
    for i in range(N-1):
        if cnt<dep:
            cnt += 1
            ans[i] = [i+1, i+2]
        else:
            cnt = 1
            ans[i] = [1, i+2]
    for v in ans:
        print(" ".join(map(str,v)))
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,ALPHABET
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]
ALPHABET = [chr(ord('A') + i) for i in range(26)]

if __name__ == '__main__':
    examE2()

Submission status: Wrong Answer

Solution code:
def examC():
    N = I()
    A = LI()
    d0 = defaultdict(int); d0[0] = 0
    d1 = defaultdict(int); d1[0] = 0
    for i in range(N):
        if i%2==0:
            d0[A[i]] +=1
        else:
            d1[A[i]] +=1
    n0 = sorted(d0.items(),key=lambda x:x[1])
    n1 = sorted(d1.items(),key=lambda x:x[1])
#    print(n0); print(n1)
    if n0[-1][0]!=n1[-1][0]:
        ans = N - n0[-1][1] - n1[-1][1]
    else:
        ans = N - max(n0[-1][1]+n1[-2][1],n0[-2][1]+n1[-1][1])
    print(ans)
    return

def examE():
    S = SI(); N = len(S)
    if S[-1]=="1" or S[0]=="0":
        print(-1)
        return
    flag = [False]*(N//2)
    for i in range(N//2):
        if S[i]!=S[N-i-2]:
            print(-1)
            return
        if S[i]=="1":
            flag[i] = True
    print(flag)
    ans = [[] for _ in range(N-1)]
    now = 0; cur = 0
    for i in range(N-1):
        print(ans)
        if i>=(N//2):
            if cur>N-1:
                continue
            ans[cur] = [now,cur]
            cur +=1
            continue
        if flag[i]:
            ans[cur] = [i+1,i+2]
            now = i+2
            cur +=1
        else:
            for k in range(i):
                ans[cur] = [i+1, i + 2+k]
                now = i+1
                cur +=1
    for v in ans:
        print(" ".join(map(str,v)))
    return

def examE2():
    S = SI(); N = len(S)
    if S[-1]=="1" or S[0]=="0":
        print(-1)
        return
    dep = -1
    for i in range(N//2):
        if S[i]!=S[N-i-2]:
            print(-1)
            return
        if S[i]=="1":
            if dep!=-1:
                print(-1)
                return
        else:
            if dep==-1:
                dep = i
    ans = [[] for _ in range(N-1)]
    cnt = 0
    for i in range(N-1):
        if cnt<dep:
            cnt += 1
            ans[i] = [i+1, i+2]
        else:
            cnt = 1
            ans[i] = [1, i+2]
    for v in ans:
        print(" ".join(map(str,v)))
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,ALPHABET
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]
ALPHABET = [chr(ord('A') + i) for i in range(26)]

if __name__ == '__main__':
    examE2()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def main():
    s = input()[:-1]
    n = len(s)
    judge = True
    if s[n-1] == "1" or s[0] == "0":
        judge = False
    
    key = -1
    for i in range(n//2):
        if (int(s[i]) + int(s[n-i-2])) % 2 == 1:
            judge = False
        if s[i] == '0':
            if key == -1:
                key = i
            else:
                judge = False
    
    if judge:
        if key == -1:
            ans = [[int(x)+1, int(x)+2] for x in range(n-1)]
        else:
            c = 0
            ans = []
            par = 1
            for i in range(2, n+1):
                ans.append([par, i])
                c += 1
                if c == key:
                    par = 1
                    c = 0
                else:
                    par = i
        
        for x, y in ans:
            print(x, y)
    else:
        print(-1)



    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    s = "0" + input()
    ans = []
    f = True
    for i in range(len(s)//2):
        if s[i] != s[len(s)-1-i]:
            f = False
            break
    if f:
        ans = []
        p = len(s)-1
        for i in reversed(range(1, len(s)-1)):
            c = s[i]
            ans.append([i, p])
            if c == "1":
                p = i
        for u, v in ans:
            print(u, v)
    else:
        print(-1)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from math import ceil
S = input().rstrip()
LS = len(S)
if S[0]==0:
    print(-1)
    exit()
z = 0
for i in range(len(S)):
    if S[-1-i] == "0": z += 1
    else: break
S = S[:len(S)-z]
L = len(S)
if S[:L//2] != "".join(list(reversed(S[ceil(L/2):]))):
    print(-1)
    exit()
s0, cnt, p, k = "1", 1, 0, 1
D = []
for s in S[1:]:
    if s==s0:
       cnt += 1
    else:
        if p == 0:
            for _ in range(cnt):
                D.append((k, k+1))
                k += 1
            p = 1
        else:
            for j in range(1,cnt+2):
                D.append((k,k+j))
            k += cnt + 1
            p = 0
        cnt = 1
    s0 = s
if p==0 and cnt>1:
    for _ in range(cnt):
        D.append((k, k + 1))
        k += 1
if k!=LS: print(-1); exit()
else:
    for x, y in D:
        print(x,y)

Submission status: Wrong Answer

Solution code:
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

s=list(map(int,list(input())))
n=len(s)
# print(s)
if s[-1]==1 or s[0]==0:
    print(-1)
    quit()

for i in range(n-1):
    if s[i]!=s[-2-i]:
        print(-1)
        quit()
s[-1]=1
now=n
for i in range(n-1)[::-1]:
    print(i+1,now)
    if s[i]==1:
        now=i

Submission status: Wrong Answer

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
INF =  float("inf")
import bisect

s = input()
n = len(s)

if s[n-1] == "1" or s[0] == "0":
    print(-1)
    sys.exit()

for i in range((n-1) // 2):
    if s[i] != s[n-2-i]:
        print(-1)
        sys.exit()

j = 0
for i in range(1,n):
    if i == "1":
        for k in range(j,i):
            print(j+1,i+1)
        j = i

for k in range(j+1,n):
    print(j+1,k+1)

Submission status: Wrong Answer

Solution code:
S = input()

N = len(S)

if S[-1] == '1':
    print(-1)
    exit()
if N == 2:
    if S == '10':
        print(1, 2)
    else:
        print(-1)
    exit()

if S == '1'*(N-1) + '0':
    for i in range(N-1):
        print(i+1, i+2)
elif S == '1' + '0'*(N-3) + '1' + '0':
    for i in range(2, N+1):
        print(1, i)

Submission status: Wrong Answer

Solution code:
s=input()
n=len(s)
f=1
if s[-1]=="1":
  f=0
for i in range(n-1):
  if s[i]!=s[-2-i]:
    f=0
    break
    
s=s[:-1]+"1"
if f:
  k=0
  for i in range(n):
    if s[i]=="1":
      for j in range(k,i):
        print(j+1,i+1)
      k=i
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
s = input().strip()
n = len(s)
s = "0"+s
flag = 0
if s[n]=="1" or s[1]=="0":
    flag = 1
else:
    for i in range(1,n):
        if s[i]!=s[n-i]:
            flag = 1
            break
if flag==1:
    print(-1)
else:
    A = [1]
    for i in range(2,n):
        if s[i]=="1":
            while A:
                print(A.pop(),i)
        else:
            A.append(i)
    print(n-1,n)

Submission status: Wrong Answer

Solution code:
s = input().strip()
n = len(s)
s = "0"+s
flag = 0
if s[n]==1 or s[1]==0:
    flag = 1
else:
    for i in range(1,n):
        if s[i]!=s[n-i]:
            flag = 1
            break
if flag==1:
    print(-1)
else:
    A = [1]
    for i in range(2,n):
        if s[i]=="1":
            while A:
                print(A.pop(),i)
        else:
            A.append(i)
    print(n-1,n)

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""

s = input()[:-1]

if s[0] == "1" and s[-1] == "0":
	k = (len(s)-2)//2

	for i in range(k):
		if s[i] != s[-(2 + i)]:
			print(-1)
			exit()
	else:
		
		la = len(s)

		for i in range(la-2,-1,-1):
			if s[i] == "1":
				print(i+1,la)
				la = i+1
			else:
				print(i+1,1)
else:
	print(-1)

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""

s = input()[:-1]

if s[0] == "1" and s[-1] == "0":
	k = (len(s)-2)//2

	for i in range(k):
		if s[i] != s[-(2 + i)]:
			print(-1)
			exit()
	else:
		
		la = len(s)

		for i in range(la-2,-1,-1):
			if s[i] == "1":
				print(i+1,la)
				la = i+1
			else:
				print(i+1,len(s))
else:
	print(-1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    S = input()
    N = len(S)
    if S[0] == '0' or S[-1] == '1':
        print(-1)
        return
    cnt = 0
    flag = True
    for i in range(N - 1):
        if S[i] != S[N - i - 2]:
            flag = False
            break
        if S[i] == '1':
            cnt += 1
    if not flag:
        print(-1)
        return
    
    edge = []
    for i in range(cnt):
        edge.append((i + 1,i + 2))
    now = cnt + 2
    for i in range(int(N//2)):
        if S[i] == '0':
            edge.append((i + 1,now))
            now += 1
            if i + 1 != cnt - i + 1:
                edge.append((cnt - i + 1,now))
                now += 1
                
    if now == N + 1:
        print('\n'.join(' '.join(map(str,a)) for a in edge))
    else:
        print(-1)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
s = list(input())
n = len(s)
if s[-1] == "1":
    print(-1)
    exit()
if s[:-1] != s[:-1][::-1]:
    print(-1)
    exit()
if s[0] == "0":
    print(-1)
    exit()
    
before = -1
for i in range(n // 2):
    if s[i] == "1":
        num = i - before
        for j in range(num):
            print(before+2+j, i+2)
        before = i

for j in range(n-2-before):
    print(before+2, before+3+j)

Submission status: Wrong Answer

Solution code:
s = list(input())
n = len(s)
if s[-1] == "1":
    print(-1)
    exit()
if s[:-1] != s[:-1][::-1]:
    print(-1)
    exit()
before = -1
for i in range(n // 2):
    if s[i] == "1":
        num = i - before
        for j in range(num):
            print(before+2+j, i+2)
        before = i

for j in range(n-2-before):
    print(before+2, before+3+j)

Submission status: Wrong Answer

Solution code:
S = input()

def check(S):
    size = len(S)
    if S[0]=="0" or S[-1]=="1":
        return False
    else:
        for i in range(size-1):
            a, b = i, size-i-2
            if (S[a]=="1" and S[b]=="0") or (S[a]=="0" and S[b]=="1"):
                return False
        return True

if check(S):
    N = len(S)
    l = [1]
    p = False
    for i in range(2, N+1):
        if p:
            l.append(i)
            p = False
        else:
            print(l[-1], i)
            if S[i-1]=="1":
                p = True
    sl = len(l)
    for i in range(sl-1):
        print(l[i], l[i+1])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
S = input()

def check(S):
    size = len(S)
    if S[0]=="0" or S[-1]=="1":
        return False
    else:
        for i in range(size-1):
            a, b = i, size-i-2
            if (S[a]=="1" and S[b]=="0") or (S[a]=="0" and S[b]=="1"):
                return False
        return True

if check(S):
    N = len(S)
    l = [1]
    for i in range(2, N+1):
        if S[i-1]=="0":
            l.append(i)
        else:
            print(l[-1], i)
    sl = len(l)
    for i in range(sl-1):
        print(l[i], l[i+1])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
def solve():
    s = input()
    n = len(s)
    if s[-1]=="1" or s[0]=="0":
        print(-1)
        return
    else:
        l = [1]+list(map(int, s))
        v = 0
        a, b = 0, 0
        for i in range(1, 1+n):
            if not i<=n-i:break

            if (l[i]==1 and l[n-i]==0) or (l[i]==0 and l[n-i]==1):
                print(-1)
                return
            elif l[i]==1 and l[n-i]==1:
                a, b = i, n-i

        chk = True
        for i in range(2, a):
            if l[i]==0:
                chk=False
            else:
                if chk:
                    v += 1
                else:
                    print(-1)
                    return

        for i in range(1, v+1):
            print(i, i+1)
        for i in range(v+2, a+1):
            print(1, i)
        for i in range(a+1, n+1):
            print(b, i)


if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
def solve():
    s = input()
    n = len(s)
    if s[-1]=="1":
        print(-1)
        return
    else:
        l = [0]+list(map(int, s))
        seq = True
        v = 0
        for i in range(1, 1+n):
            if not i<=n-i:break
            if i==1 and l[i]==0:
                print(-1)
                return

            if l[i]==0 and l[n-i]==0:
                seq = False
            elif l[i]==0 or l[n-i]==0:
                print(-1)
                return
            elif l[i]==1 and l[n-i]==1:
                if seq:
                    v += 1
                else:
                    print(-1)
                    return
        
        for i in range(1, 1+v):
            print(i, i+1)
        
        for i in range(1+v, n):
            print(1, i+1)


if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
s = list(input())
n = len(s)
if s[n - 1] == "1" or s[0] == "0":
    print(-1)
    exit()
for i in range((n - 1) // 2):
    if not s[i] == s[n - 2 - i]:
        print(-1)
        exit()
l = n - s.count("0") + 1
x = [0] * l
j = 0
for i in range(n // 2):
    if s[i] == "1":
        j += 1
    else:
        x[j] += 1
        x[l - 1 - j] += 1
        if j == l - 1 - j and n % 2 == 0:
            x[j] -= 1
for i in range(l - 1):
    print(i + 1, i + 2)
k = n - s.count("0") + 2
for i in range(l):
    for _ in range(x[i]):
        print(i + 1, k)
        k += 1

Submission status: Wrong Answer

Solution code:
s = list(input())
n = len(s)
if s[n - 1] == "1" or s[0] == "0":
    print(-1)
    exit()
for i in range((n - 1) // 2):
    if not s[i] == s[n - 2 - i]:
        exit()
l = n - s.count("0") + 1
x = [0] * l
j = 0
for i in range(n // 2):
    if s[i] == "1":
        j += 1
    else:
        x[j] += 1
        x[l - 1 - j] += 1
        if j == l - 1 - j and n % 2 == 0:
            x[j] -= 1
for i in range(l - 1):
    print(i + 1, i + 2)
k = n - s.count("0") + 2
for i in range(l):
    for _ in range(x[i]):
        print(i + 1, k)
        k += 1

Submission status: Wrong Answer

Solution code:
s = list(input())
n = len(s)
if s[n - 1] == "1" or s[0] == "0":
    print(-1)
    exit()
for i in range((n - 1) // 2):
    if not s[i] == s[n - 2 - i]:
        exit()
l = n - s.count("0") + 1
x = [0] * l
j = 0
for i in range(n // 2):
    if s[i] == "1":
        j += 1
    else:
        x[j] += 1
        x[l - 1 - j] += 1
for i in range(l - 1):
    print(i + 1, i + 2)
k = n - s.count("0") + 2
for i in range(l):
    for _ in range(x[i]):
        print(i + 1, k)
        k += 1

Submission status: Wrong Answer

Solution code:
s = input()

if s[-1] == '1' or s[:-1] != s[:-1][::-1]:
    print(-1)
    exit(0)

edges = []
head = 0
for idx, i in enumerate(s[:-1]):
    edges.append([head, idx + 1])
    if i == '1':
        head = idx + 1
for i, j in edges:
    print(i + 1, j + 1)

Submission status: Wrong Answer

Solution code:
def show_g(g):
    import matplotlib.pyplot as plt
    import networkx as nx

    G = nx.Graph()
    for v in range(len(g)):
        G.add_node(v + 1)

    for v in range(len(g)):
        for u in g[v]:
            G.add_edge(v + 1, u + 1)

    nx.draw_networkx(G)
    plt.show()


def print_edges(g, *, show=False):
    n = len(g)
    for v in range(n):
        for u in g[v]:
            print(v + 1, u + 1)
    if show:
        show_g(g)


def main():
    from itertools import tee
    import re

    S = input()
    N = len(S)

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

    g = tuple(set() for _ in range(N))

    K = len(re.split('0+', S))
    if K == 2:
        # 11...0
        for v in range(N - 1):
            g[v].add(v + 1)
        print_edges(g)
        return
    elif K == 3:
        # WA提出は11...00...11...00...11...0のように
        # 途中に複数の0区間をとるものを許していた
        # 事前にKの大きさを調べることで、0区間を途中に1つしか含まないようにした

        # 11...00...11...0
        # m:=中央の頂点につながる手の最大長さ
        # 切り出せる長さは、中央と手の間の辺を切り離したときに最大値mをとり
        # それ未満の任意の長さは手を末端から適当な長さ取ることで作れる
        # [1,m]の断片を作れる <-> [N-m,N-1]の断片も同時に作れる
        # [m+1,N-m-1]の断片は作れない
        m = -1
        fix = False
        for i in range(N - 1):
            if (S[i] == '1') ^ (S[N - 2 - i] == '1'):
                print(-1)
                return
            if (S[i] == '1') and (not fix):
                m = i + 1
            else:
                fix = True

        vs = list(range(1, N))
        cur = 0
        while cur < len(vs):
            t = vs[cur:cur + m]  # 手
            g[0].add(t[0])  # 中心とつなぐ

            iter_v, iter_u = tee(iter(t), 2)
            next(iter_u)
            for v, u in zip(iter_v, iter_u):
                g[v].add(u)  # 手の要素の連結
            cur += m

        print_edges(g)
        return

    else:
        print(-1)
        return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    from itertools import tee

    *S, = map(int, input())
    N = len(S)

    if (S[0] == 0) or (S[-1] == 1):
        # サイズ1の連結成分は必ず作れる
        # サイズNの連結成分は決して作れない
        print(-1)
        return

    g = tuple(set() for _ in range(N))
    if S[-1] == 0 and all(x for x in S[:-1]):
        # 11...0
        for v in range(N - 1):
            g[v].add(v + 1)

        for v in range(N):
            for u in g[v]:
                print(v + 1, u + 1)
        return

    m = -1
    fix = False
    for i in range(N - 1):
        # 二つの対となるサイズの連結成分は、
        # 一方が生成できるなら、必ずもう一方も生成できる
        if S[i] ^ S[N - 2 - i]:
            print(-1)
            return

        if S[i] and (not fix):
            m = i + 1
        else:
            fix = True

    # 11...00...11....
    # mがカットで生成する最大長さ
    # CH4のような中央の核に周囲から手が伸びている状態を考える
    # 核につながっている手の長さをmとすると
    # 核と手を切り離すか、手を末端から適当な長さ切り出すことで、
    # [1,m]の断片を作れる <-> [N-m,N-1]の断片も同時に作れる
    # [m+1,N-m-1]の断片は作れない

    vs = list(range(1, N))
    cur = 0
    while cur < len(vs):
        t = vs[cur:cur + m]
        g[0].add(t[0])
        iter_v, iter_u = tee(iter(t), 2)
        next(iter_u)
        for v, u in zip(iter_v, iter_u):
            g[v].add(u)
        cur += m

    for v in range(N):
        for u in g[v]:
            print(v + 1, u + 1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
S = input()
N = len(S)
if S[0]=='0' or S[-1]=='1' or S[-2]=='0':
    print(-1)
    exit()

arr = []
for i in range(N-1):
    if S[i]=='1' and S[N-i-2]=='0':
        print(-1)
        exit()
    if 0 < i < (N+1)//2 and S[i]=='1':
        arr.append(i+1)

s = arr[0] if arr else N
ans = []
for i in range(s-1):
    ans.append('{0} {1}'.format(i+1,s))
for a,b in zip(arr, arr[1:]):
    for c in range(a+1,b+1):
        ans.append('{0} {1}'.format(a,c))
if arr:
    s = arr[-1]
    if len(arr)==1 and arr[0]==N//2:
        ans.append('{0} {1}'.format(arr[0], arr[0]+1))
        s += 1
    for i in range(s+1, N+1):
        ans.append('{0} {1}'.format(s,i))
print(*ans, sep='\n')

Submission status: Wrong Answer

Solution code:
import sys
# input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

S = list(input())
if S[-1] == '1':
    print (-1)
    exit()
if S[0] == '0':
    print (-1)
    exit()

N = len(S) - 1
n = (N + 1) // 2 #切り上げ

flag = True
tmp = -1
for i in range(n):
    if flag:
        if S[i] == S[N - 1 - i] == '1':
            tmp = i
        elif S[i] == S[N - 1 - i] == '0':
            flag = False
        else:
            print (-1)
            exit()
    else:
        if S[i] == S[N - 1 - i] == '0':
            continue
        else:
            print (-1)
            exit()

if tmp == 0:
    for k in range(N):
        print (1, k + 2)
    exit()

for i in range(tmp):
    print (i + 1, i + 2)
    print (N - i, N - i + 1)

print (i + 2, i + 3)
if N - i != i + 3:
    print (N - i, i + 3)
else:
    exit()

for j in range(i + 4, N - i):
    print (i + 3, j)

Submission status: Wrong Answer

Solution code:
import sys
# input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

S = list(input())
if S[-1] == '1':
    print (-1)
    exit()

N = len(S) - 1
n = (N + 1) // 2 #切り上げ

flag = True
tmp = -1
for i in range(n):
    if flag:
        if S[i] == S[N - 1 - i] == '1':
            tmp = i
        elif S[i] == S[N - 1 - i] == '0':
            flag = False
        else:
            print (-1)
            exit()
    else:
        if S[i] == S[N - 1 - i] == '0':
            continue
        else:
            print (-1)
            exit()

for i in range(tmp):
    print (i + 1, i + 2)
    print (N - i, N - i + 1)

if tmp == 0:
    for k in range(N):
        print (1, k + 2)
    exit()



print (i + 2, i + 3)
if N - i != i + 3:
    print (N - i, i + 3)
else:
    exit()

for j in range(i + 4, N - i):
    print (i + 3, j)

Submission status: Wrong Answer

Solution code:
import sys
# input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

S = list(input())
if S[-1] == '1':
    print (-1)
    exit()

N = len(S) - 1
n = (N + 1) // 2 #切り上げ

flag = True
tmp = -1
for i in range(n):
    if flag:
        if S[i] == S[N - 1 - i] == '1':
            tmp = i
        elif S[i] == S[N - 1 - i] == '0':
            flag = False
        else:
            print (-1)
            exit()
    else:
        if S[i] == S[N - 1 - i] == '0':
            continue
        else:
            print (-1)
            exit()

for i in range(tmp):
    print (i + 1, i + 2)
    print (N - i, N - i + 1)

print (i + 2, i + 3)
if N - i != i + 3:
    print (N - i, i + 3)
else:
    exit()

for j in range(i + 4, N - i):
    print (i + 3, j)

Submission status: Wrong Answer

Solution code:
s=input()
n=len(s)
if s[-1]=='1':
    print(-1)
    exit()
if s[:-1]!=s[:-1][::-1]:
    print(-1)
    exit()
if s[0]=='0':
    print(-1)
    exit()
z=0
for i in range(n-2):
    if s[i]!=s[i+1]:
        z+=1
if z==0 or z==2:
    k=[]
    for i in range((n-1)//2+1):
        if s[i]=='1':
            k.append(i)
    mk=max(k)+1
    for i in range(mk):
        print(i+1,i+2)
    for i in range(n-1-mk):
        print(1,i+mk+1+1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
s=input()
if s[-1]=='1':
  print(-1)
elif s[0]=='0':
  print(-1)
else:
  s=s[:-1]
  l=len(s)
  for i in range(l):
    if s[i]!=s[l-i-1]:
      print(-1)
      exit()
  length=0
  pos=-1
  for i in range(l//2+1):
    if s[i]=='1':
      length+=1
    else:
      pos=i
      break
  if pos==-1:
    for i in range(l):
      print(i+1,i+2)
  else:
    for i in range(i,l//2+1):
      if s[i]=='1':
        print(-1)
        exit()
    root=1
    cnt=0
    child=root+1
    for _ in range(l):
      print(root,child+cnt)
      cnt+=1
      if cnt<=length:
        cnt=0
        child+=length

Submission status: Wrong Answer

Solution code:
s=input()
if s[-1]=='1':
  print(-1)
elif s[0]==0:
  print(-1)
else:
  s=s[:-1]
  l=len(s)
  for i in range(l):
    if s[i]!=s[l-i-1]:
      print(-1)
      exit()
  length=0
  pos=-1
  for i in range(l//2+1):
    if s[i]=='1':
      length+=1
    else:
      pos=i
      break
  if pos==-1:
    for i in range(l):
      print(i+1,i+2)
  else:
    for i in range(i,l//2+1):
      if s[i]=='1':
        print(-1)
        exit()
    root=1
    cnt=0
    child=root+1
    for _ in range(l):
      print(root,child+cnt)
      cnt+=1
      if cnt<=length:
        cnt=0
        child+=length