답안 #776031

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
776031 2023-07-07T08:47:05 Z 이동현(#9992) The Collection Game (BOI21_swaps) C++17
0 / 100
1 ms 976 KB
//
// --- Sample implementation for the task swaps ---
//
// To compile this program with the sample grader, place:
//     swaps.h swaps_sample.cpp sample_grader.cpp
// in a single folder and run:
//     g++ swaps_sample.cpp sample_grader.cpp
// in this folder.
//
#include "swaps.h"
#include <bits/stdc++.h>
using namespace std;

int ans[504];
struct Data{
    vector<int> id, mid;
    int state;
    int nxt[4];
    Data(){}
};
Data tr[10004];
int trn;

void solve(int n, int v) {
    ++trn;
    for(int i = 1; i <= n; ++i){
        tr[1].id.push_back(i);
    }
    int m = n;
    while(__builtin_popcount(m) != 1){
        ++m;
        tr[1].id.push_back(m);
    }
    while(tr[1].state != 3){
        vector<int> ask;
        for(int i = trn; i >= 1; --i){
            int lsz = (int)tr[i].id.size() / 2;
            int rsz = ((int)tr[i].id.size() + 1) / 2;
            if(tr[i].state == 3) continue;
            if(lsz + rsz <= 1){
                if((int)tr[i].id.size()){
                    // cout << "SET " << tr[i].id[0] << ' ' << 0 << endl;
                    ans[tr[i].id[0]] = 0;
                }
                tr[i].state = 3;
                continue;
            }
            if(tr[i].state == 2){
                if(tr[tr[i].nxt[3]].state == 3){
                    for(auto&j:tr[tr[i].nxt[3]].id){
                        // cout << "ANSADD " << i << ' ' << j << ' ' << lsz / 2 << endl;
                        ans[j] += lsz / 2;
                    }
                    sort(tr[i].id.begin(), tr[i].id.end(), [&](int&x, int&y){return ans[x] < ans[y];});
                    // if(tr[i].id == vector<int>{7, 5}){
                    //     cout << "WEF " << ans[5] << ' ' << ans[7] << endl;
                    // }
                    // cout << "RES\n";
                    // for(auto&j:tr[i].id){
                    //     cout << j << ' ';
                    // }
                    // cout << endl;
                    tr[i].state = 3;
                }
            }
            else if(tr[i].state == 1){
                if(tr[tr[i].nxt[1]].state == 3 && tr[tr[i].nxt[2]].state == 3){
                    for(int j = 0; j < lsz; ++j){
                        if(j < lsz / 2){
                            // cout << "ANS " << i << ' ' << tr[tr[i].nxt[1]].id[j] << ' ' << j << endl;
                            ans[tr[tr[i].nxt[1]].id[j]] = j;
                        }
                        else{
                            tr[i].mid.push_back(tr[tr[i].nxt[1]].id[j]);
                        }
                    }
                    for(int j = 0; j < rsz; ++j){
                        if(j + (rsz + 1) / 2 < rsz){
                            tr[i].mid.push_back(tr[tr[i].nxt[2]].id[j]);
                        }
                        else{
                            // cout << "ANS " << i << ' ' << tr[tr[i].nxt[2]].id[j] << ' ' << lsz + j << endl;
                            ans[tr[tr[i].nxt[2]].id[j]] = lsz + j;
                        }
                    }
                    tr[++trn].id = tr[i].mid;
                    tr[i].nxt[3] = trn;
                    tr[i].state = 2;
                }
            }
            else if(tr[i].state == 0){
                ask.push_back(i);
            }
        }
        if(!(int)ask.size()) continue;
        for(auto&i:ask){
            int lsz = (int)tr[i].id.size() / 2;
            for(int j = 0; j < lsz; ++j){
                if(tr[i].id[j] > n || tr[i].id[j + lsz] > n) continue;
                schedule(tr[i].id[j], tr[i].id[j + lsz]);
            }
        }
        auto rv = visit();
        int rp = 0;
        for(auto&i:ask){
            int lsz = (int)tr[i].id.size() / 2;
            for(int j = 0; j < lsz; ++j){
                if(tr[i].id[j] > n || tr[i].id[j + lsz] > n){
                    if(tr[i].id[j] < tr[i].id[j + lsz]){
                        swap(tr[i].id[j], tr[i].id[j + lsz]);
                    }
                }
                else{
                    if(!rv[rp]){
                        swap(tr[i].id[j], tr[i].id[j + lsz]);
                    }
                    ++rp;
                }
            }
        }

        for(auto&i:ask){
            int lsz = (int)tr[i].id.size() / 2;
            tr[i].state = 1;
            ++trn;
            tr[i].nxt[1] = trn;
            for(int j = 0; j < lsz; ++j) tr[trn].id.push_back(tr[i].id[j]);
            ++trn;
            tr[i].nxt[2] = trn;
            for(int j = lsz; j < (int)tr[i].id.size(); ++j){
                tr[trn].id.push_back(tr[i].id[j]);
            }
        }
    }

    vector<int> rv(n);
    for(int i = 1; i <= n; ++i){
        // cout << ans[i] << endl;
        rv[ans[i] - (m - n)] = i;
    }
    answer(rv);
}
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 976 KB Not correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 976 KB Not correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 976 KB Not correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 976 KB Not correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 976 KB Not correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 976 KB Not correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 976 KB Not correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 976 KB Not correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 976 KB Not correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 976 KB Not correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 976 KB Not correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 976 KB Not correct
2 Halted 0 ms 0 KB -