oj.uz

Submission #762430

# Submission time Handle Problem Language Result Execution time Memory
762430 2023-06-21T11:49:01 Z goodbyehanbyeol On the Grid (FXCUP4_grid) C++17
0 / 100
 0 ms 212 KB 
#include "grid.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
vector<int> ans;
int ourAns[1002];
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);

    for(int turn=1; turn<n; turn++){
        vector<int> unusedIndex, unusedValue;
        for(int i=0; i<n; i++) if(!usedIndex[i]) unusedIndex.push_back(i);
        for(int i=1; i<=n; i++) if(!usedValue[i]) unusedValue.push_back(i);

        vector<bool> rotatePlacement (n);
        vector<int> vec (n);
        vector<int> oldVec (n);
        for(int i=0; i<n; i++){
            if(usedIndex[i]) vec[i] = ourAns[i];
        }
        for(int i=0; i<(int)unusedIndex.size(); i++) vec[unusedIndex[i]] = unusedValue[i];

        int val = query(vec);
        if(val == n+1){
            for(int i=0; i<n; i++){
                if(!usedIndex[i]){
                    int idx = i, ai = val - vec[idx];
                    ans[idx] = ai;
                }
            }
            break;
        }

        while(1){
            int criteria = val - n; /// 여기서부터 rotate 함
            int recentIdx = -1, firstVal = -1;
            int cnt = 0;
            oldVec = vec;
            for(int i=n-1; i>=0; i--){
                if(usedIndex[i] || vec[i] < criteria) continue;
                if(firstVal == -1) firstVal = vec[i];
                else vec[recentIdx] = vec[i];
                recentIdx = i;
                cnt++;
            }
            vec[recentIdx] = firstVal;

            if(cnt == 1){ /// 넘은 값이 하나밖에 없는 경우
                int idx = recentIdx;
                int ai = val - vec[idx]; /// 이 사람의 값
                int bi = n + 1 - ai; /// 합 보정
                ourAns[idx] = bi, ans[idx] = ai, usedIndex[idx] = usedValue[bi] = 1;
                break;
            }

            int val2 = query(vec);
            if(val2 == val-1){
                val = val2;
                if(val == n+1){
                    for(int i=0; i<n; i++){
                        if(!usedIndex[i]){
                            int idx = i, ai = val - vec[idx];
                            ans[idx] = ai;
                        }
                    }
                    break;
                }
                val = val2;
                continue;
            }

            int idx;
            for(int i=0; i<n; i++) if(oldVec[i] < vec[i]) idx = i;
            int ai = val2 - vec[idx]; /// 이 사람의 값
            int bi = n + 1 - ai; /// 합 보정
            ourAns[idx] = bi, ans[idx] = ai, usedIndex[idx] = usedValue[bi] = 1;
            break;
        }
    }

    if(count(ans.begin(), ans.end(), 0)){
        ans[find(ans.begin(), ans.end(), 0) - ans.begin()] = n*(n+1)/2 - accumulate(ans.begin(), ans.end(), 0);
    }

	return ans;
}

Compilation message

grid.cpp: In function 'std::vector<int> SortDisks(int)':
grid.cpp:90:36: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   90 |             int ai = val2 - vec[idx]; /// 이 사람의 값
      |                                    ^

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -