Submission #762480

#	Time	Username	Problem	Language	Result	Execution time	Memory
762480		goodbyehanbyeol	On the Grid (FXCUP4_grid)	C++17	100 / 100	19 ms	344 KiB

grid

#include "grid.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
vector<int> ans;
bool usedIndex[1002], usedValue[1002];

int query(vector<int> vec){
    /// 실제: max(Ai + n - 1 - Bi), 이상: max(Ai + Bi)
    /// 따라서 수정이 필요

    vector<int> toQuery(n);
    for(int i=0; i<n; i++) toQuery[n-vec[i]] = i;
    return PutDisks(toQuery) + 1;
}

vector<int> SortDisks(int N){
    n = N;
    ans.resize(n);

    vector<int> vec(n);
    for(int i=0; i<n; i++) vec[i] = i+1;

    int val = -1, lastval = -1, exceed = -1; /// 바꾸고 난 뒤 val, 바꾸기 전 val, 넘었을 때 넘은 위치
    while(true){
        lastval = val, val = query(vec);

        if(val == n+1){ /// 모든 게 완벽하게 짝지어짐
            for(int i=0; i<n; i++) if(!usedIndex[i]){
                int ai = val - vec[i];
                ans[i] = ai;
            }
            break;
        }

        int criteria = val - n; /// rotate에 들어가는 기준
        int findingCnt = 0;

        for(int i=0; i<n; i++) if(!usedIndex[i] && vec[i] >= criteria) findingCnt++;

        if(findingCnt == 1 || (lastval != -1 && val > lastval-1)){ /// 남은 게 하나 or 1 감소하지 않아 exceed 처리
            int idx = 0;
            if(findingCnt == 1) while(usedIndex[idx] || vec[idx] < criteria) idx++;
            else idx = exceed;
            int ai = val - vec[idx];
            int bi = n + 1 - ai;
            int changedPosition = find(vec.begin(), vec.end(), bi) - vec.begin();
            swap(vec[idx], vec[changedPosition]), ans[idx] = ai, usedIndex[idx] = usedValue[bi] = 1;
            exceed = changedPosition;
            val = lastval;
            continue;
        }

        /// 이제 남은 게 여러 개고 1 감소한 상황

        vector<pair<int, int> > pairVec;
        for(int i=0; i<n; i++) if(!usedIndex[i] && vec[i] >= criteria){
            pairVec.push_back(make_pair(vec[i], i));
        }
        sort(pairVec.begin(), pairVec.end());

        /// 한 칸씩 오른쪽으로 민다
        for(int i=0; i<(int)pairVec.size()-1; i++){
            vec[pairVec[i+1].second] = pairVec[i].first;
        }
        vec[exceed = pairVec[0].second] = pairVec.back().first;
    }

	return ans;
}

• Subtask 1: 12 / 12
• Subtask 2: 31 / 31
• Subtask 3: 57 / 57