QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#542620	#8939. Permutation	ucup-team1231^#	RE	9ms	10628kb	Python3	2.7kb	2024-09-01 03:15:06	2024-09-01 03:15:07

Judging History

This is the latest submission verdict.

[2024-09-01 03:15:07]
Judged

Verdict: RE
Time: 9ms
Memory: 10628kb

Show

[2024-09-01 03:15:06]
Submitted

answer

import sys
T = int(input())
def calc(u):
    if u<=1: return 0
    if u==2: return 1
    if u==3: return 2
    return 3+calc((u+3)//4)
def qry(a,b):
    print('?',a,b)
    sys.stdout.flush()
    return int(input())
def sol():
    n = int(input())
    L, R = 1, n
    while R-L+1 >= 4:
        u = R-L+1
        fid = [L+u*i//4 for i in [0,1,2,3,4]]
        x = qry(L, R)
        # [fid[t],fid[t+1])
        inseg = lambda t,u: fid[t]<=u<fid[t+1]
        if inseg(0,x):
            if qry(fid[0],fid[2]-1) == x:
                if qry(fid[0],fid[1]-1) == x:
                    L, R = fid[0], fid[1]-1
                else:
                    L, R = fid[1], fid[2]-1
            else:
                if qry(fid[0],fid[3]-1) == x:
                    L, R = fid[2], fid[3]-1
                else:
                    L, R = fid[3], fid[4]-1
        elif inseg(1,x):
            if qry(fid[0], fid[3]-1) == x:
                if qry(fid[1], fid[2]-1) == x:
                    L, R = fid[1], fid[2]-1
                else:
                    L, R = fid[2], fid[3]-1
            else:
                if qry(fid[0], fid[3]-1) == x:
                    L, R = fid[0], fid[1]-1
                else:
                    L, R = fid[3], fid[4]-1
        elif inseg(2,x):
            if qry(fid[0], fid[3]-1) == x:
                if qry(fid[2], fid[3]-1) == x:
                    L, R = fid[2], fid[3]-1
                else:
                    L, R = fid[1], fid[2]-1
            else:
                if qry(fid[0], fid[3]-1) == x:
                    L, R = fid[0], fid[1]-1
                else:
                    L, R = fid[3], fid[4]-1
        else:
            if qry(fid[2],fid[4]-1) == x:
                if qry(fid[3],fid[4]-1) == x:
                    L, R = fid[3], fid[4]-1
                else:
                    L, R = fid[2], fid[3]-1
            else:
                if qry(fid[1],fid[4]-1) == x:
                    L, R = fid[1], fid[2]-1
                else:
                    L, R = fid[0], fid[1]-1

    ans = -1
    if R-L+1 == 3:
        x = qry(L,L+2)
        if x == L:
            L = x+1
        elif x == R:
            R = x-1
        else:
            assert x == L+1
            u = qry(L,x)
            if u == x:
                ans = L
            else:
                ans = R
    if ans == -1:
        if R-L+1 == 2:
            ans = qry(L,R)^L^R
        else:
            assert R-L+1 == 1
            ans = L
    print('!',ans)
    sys.stdout.flush()
import math
for i in range(1,100):
    c = calc(i)
    u = math.ceil(math.log2(i)*1.5)
    if c>u:
        print(i,c,u)
for _ in range(T):
    sol()

Source code, Language: Python3

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 9ms

memory: 10628kb

input:

output:

result:

ok Correct (3 test cases)

Test #2:

score: -100

Dangerous Syscalls

input:

output: