oj.uz

Submission #776022

# Submission time Handle Problem Language Result Execution time Memory
776022 2023-07-07T08:36:00 Z 이동현(#9992) The Collection Game (BOI21_swaps) C++17
0 / 100
 1 ms 1016 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);
    }
    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){
                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(!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]] = i;
    }
    answer(rv);
}

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 976 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1008 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #3-1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1016 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #3-2
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1016 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #4-1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1012 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #4-2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1012 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #5-1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 976 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #5-2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 976 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #6-1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 976 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #6-2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 976 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #7-1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 976 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #7-2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 976 KB Not correct
2 Halted 0 ms 0 KB -