oj.uz

Submission #732229

# Submission time Handle Problem Language Result Execution time Memory
732229 2023-04-28T17:43:15 Z Stickfish The Collection Game (BOI21_swaps) C++17
35 / 100
 35 ms 444 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 <algorithm>
#include <iostream>
#include <cassert>
using namespace std;

void get_stree_nodes(int d, int l, int r, vector<vector<pair<int, int>>>& ans) {
    if (r - l == 1)
        return;
    if (d >= ans.size())
        ans.push_back({});
    ans[d].push_back({l, r});
    int m = (l + r) / 2;
    get_stree_nodes(d + 1, l, m, ans);
    get_stree_nodes(d + 1, m, r, ans);
}

void solve(int N, int V) {
    vector<int> v(N);
    for (int i = 0; i < N; ++i)
        v[i] = i + 1;
    vector<vector<pair<int, int>>> nds;
    get_stree_nodes(0, 0, N, nds);
    for (int d = nds.size() - 1; d >= 0; --d) {
        vector<pair<pair<int, int>, pair<int, int>>> sgs;
        for (auto [l, r] : nds[d]) {
            int m = (l + r) / 2;
            sgs.push_back({{l, m}, {m, r}});
        }
        // cout << endl;
        for (auto& [s1, s2] : sgs) {
            if (s2.second - s2.first != s1.second - s1.first) {
                assert(s2.second - s2.first - 1 == s1.second - s1.first);
                --s2.second;
                // cout << "(" << s1.first << ' ' << s1.second << ' ' << s2.first << ' ' << s2.second << ") ";
            }
        }
        // cout << endl;
        bool cont = true;
        while (cont) {
            cont = false;
            for (auto [s1, s2] : sgs) {
                if (s2.second <= s2.first)
                    continue;
                cont = true;
                for (int i = 0; i < s2.second - s2.first; ++i)
                    schedule(v[s1.first + i], v[s2.first + i]);
            }
            if (!cont)
                break;
            vector<int> vis = visit();
            int visi = 0;
            for (auto& [s1, s2] : sgs) {
                if (s2.second <= s1.first)
                    continue;
                for (int i = 0; i < s2.second - s2.first; ++i) {
                    if (!vis[visi++])
                        swap(v[s1.first + i], v[s2.first + i]);
                }
                ++s1.first;
                --s2.second;
            }
        }
        vector<pair<int, int>> leftover;
        for (auto& p : nds[d]) {
            if ((p.second - p.first) % 2) {
                leftover.push_back({p.first, p.second - 1});
            }
            else
                leftover.push_back({-1, -1});
        }
        while (true) {
            bool isleft = false;
            for (auto x : leftover) {
                isleft |= x.first < x.second;
            }
            if (!isleft)
                break;
            for (size_t i = 0; i < leftover.size(); ++i) {
                if (leftover[i].first >= leftover[i].second)
                    continue;
                schedule(v[leftover[i].first], v[leftover[i].second]);
            }
            vector<int> vis = visit();
            int visi = 0;
            for (size_t i = 0; i < leftover.size(); ++i) {
                if (leftover[i].first >= leftover[i].second)
                    continue;
                if (!vis[visi++])
                    swap(v[leftover[i].first], v[leftover[i].second]);
                ++leftover[i].first;
            }
        }
    }
    answer(v);
}

Compilation message

swaps.cpp: In function 'void get_stree_nodes(int, int, int, std::vector<std::vector<std::pair<int, int> > >&)':
swaps.cpp:19:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     if (d >= ans.size())
      |         ~~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 4 ms 208 KB Correct
3 Correct 16 ms 288 KB Correct
4 Correct 26 ms 320 KB Correct
5 Correct 25 ms 332 KB Correct
6 Correct 27 ms 428 KB Correct
7 Correct 31 ms 336 KB Correct
8 Correct 35 ms 444 KB Correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 3 ms 208 KB Correct
3 Correct 10 ms 304 KB Correct
4 Correct 27 ms 320 KB Correct
5 Correct 30 ms 332 KB Correct
6 Correct 28 ms 412 KB Correct
7 Correct 26 ms 316 KB Correct
8 Correct 34 ms 320 KB Correct
9 Correct 27 ms 328 KB Correct
10 Correct 29 ms 320 KB Correct
11 Correct 28 ms 316 KB Correct
12 Correct 27 ms 336 KB Correct
13 Correct 26 ms 316 KB Correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 4 ms 208 KB Correct

Subtask #4
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 4 ms 208 KB Correct
3 Correct 1 ms 208 KB Correct
4 Correct 3 ms 208 KB Correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 3 ms 208 KB Correct
3 Correct 11 ms 288 KB Correct
4 Correct 26 ms 320 KB Correct

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 3 ms 208 KB Correct
3 Correct 11 ms 288 KB Correct
4 Correct 26 ms 320 KB Correct
5 Correct 1 ms 208 KB Correct
6 Correct 2 ms 208 KB Correct
7 Correct 9 ms 304 KB Correct
8 Correct 31 ms 396 KB Correct
9 Correct 23 ms 340 KB Correct
10 Correct 35 ms 324 KB Correct
11 Correct 31 ms 412 KB Correct
12 Correct 27 ms 324 KB Correct
13 Correct 1 ms 208 KB Correct
14 Correct 3 ms 208 KB Correct
15 Correct 13 ms 304 KB Correct
16 Correct 26 ms 320 KB Correct

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Correct
2 Correct 2 ms 208 KB Correct
3 Correct 9 ms 308 KB Correct
4 Correct 26 ms 320 KB Correct
5 Runtime error 19 ms 324 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Correct
2 Correct 2 ms 208 KB Correct
3 Correct 9 ms 308 KB Correct
4 Correct 26 ms 320 KB Correct
5 Runtime error 19 ms 324 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -

Subtask #9
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 3 ms 208 KB Correct
3 Correct 12 ms 288 KB Correct
4 Correct 29 ms 316 KB Correct
5 Runtime error 19 ms 296 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 3 ms 208 KB Correct
3 Correct 12 ms 288 KB Correct
4 Correct 29 ms 316 KB Correct
5 Runtime error 19 ms 296 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 3 ms 208 KB Correct
3 Correct 10 ms 416 KB Correct
4 Correct 26 ms 320 KB Correct
5 Runtime error 21 ms 380 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -

Subtask #12
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct
2 Correct 3 ms 208 KB Correct
3 Correct 10 ms 416 KB Correct
4 Correct 26 ms 320 KB Correct
5 Runtime error 21 ms 380 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -