시도 횟수: 1회

해결한 시간: 00:00

문제 번역(GPT)

핵심 아이디어

<aside> 💡

1. $[1, n]$구간의 합과 기존 순열의 합의 차를 통해 $[l,r]$구간의 길이를 알 수 있다.
2. $l$만 찾으면 구간 길이를 더하여 $r$를 찾을 수 있다. </aside>

$l$을 찾을 때 $[1, k]$로 쿼리를 날린다.(시작점을 $1$로 고정) $k$가 $[l, r]$구간에 포함되는지 포함되지 않는지를 통해서 이분탐색을 한다.

코드

#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
using namespace std;
typedef long long ll;

int qry(int q, int l, int r)
{
    cout << q << " " << l <<" " << r << endl;

    int ret;
    cin >> ret;
    return ret;
}

int n;

void solve()
{
    cin >> n;
    
    int tsumP = qry(1, 1, n);
    int tsumA = qry(2, 1, n);
    int tlen = tsumA-tsumP;

    tsumP = qry(1, 1, 1);
    tsumA = qry(2, 1, 1);
    if(tsumA != tsumP){
        cout << "! 1 " << tlen << endl;
        return;
    }

    int l = 1;
    int r = n+1;

    while(l+1<r){
        int mid = l+r>>1;
        int sumP = qry(1, 1, mid);
        int sumA = qry(2, 1, mid);

        if(sumP==sumA) l = mid;
        else r = mid;
    }

    cout << "! " << r <<" " << r+tlen-1<<endl;
    
}

signed main()
{
    int _tc; cin >> _tc;
    while (_tc--) solve();
    return 0;
}

복기

핵심을 다 잡아 놓고 못 푼게 너무 아쉽다.

핵심 아이디어를 떠올렸다면 생각을 한번 정리하고 갈 필요가 있다.

ex) 지금까지의 해결 진척도를 생각하면서 과정을 한 문장으로 정리하기