QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#719593#5583. Color Tubesnickbelov#RE 0ms3844kbC++204.7kb2024-11-07 04:38:002024-11-07 04:38:01

Judging History

你现在查看的是最新测评结果

  • [2024-11-07 04:38:01]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3844kb
  • [2024-11-07 04:38:00]
  • 提交

answer

#include <vector>
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T>
ostream_iterator<T> oit(const string &s = " "){ return ostream_iterator<T>(cout,s.c_str()); }
inline auto rep(int l, int r) { return views::iota(min(l, r), r); }
inline auto rep(int n) { return rep(0, n); }
inline auto rep1(int l, int r) { return rep(l, r + 1); }
inline auto rep1(int n) { return rep(1, n + 1); }
inline auto per(int l, int r) { return rep(l, r) | views::reverse; }
inline auto per(int n) { return per(0, n); }
inline auto per1(int l, int r) { return per(l, r + 1); }
inline auto per1(int n) { return per(1, n + 1); }
#define A(a) begin(a),end(a)
inline auto len = ranges::ssize;

struct chash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
template<typename T, typename U> using pb_map = gp_hash_table<T, U, chash>;
template<typename T> using pb_set = gp_hash_table<T, null_type, chash>;
#define K first
#define V second

using ll = long long;
using ld = long double;

using vi = vector<int>;
using vii = vector<vector<int>>;
typedef vector<ll> vll;
using pll = pair<ll,ll>;
using pii = pair<int,int>;


void run()
{
    int n; cin >> n, ++n;

    vii stacks(n);
    for(int i : rep(n)){
        for(int x : rep(3)) {
            cin >> x;
            if(x!=0) stacks[i].push_back(x);
        }
    }

    vector<pii> ans;

    auto move = [&](int u,int v){ //from u to v
        assert(not stacks[u].empty());
        assert(len(stacks[v])<3);
        int g = stacks[u].back(); stacks[u].pop_back();
        stacks[v].push_back(g);
        ans.emplace_back(u,v);
    };
    auto is_mono = [&](int i){
        return stacks[i][0] == stacks[i][1] and stacks[i][1] == stacks[i][2];
    };
    //lets make an empty one, now first one will start empty()

    for(int i : rep(1,n)){
        while(len(stacks[i])<3 and !stacks[0].empty()) move(0,i); 
    }

    auto has = [&](const vi &v, char want){
        for(char c : v) if(c==want) return true;
        return false;
    };

    while(true){
        int emp = 0; while(!stacks[emp].empty()) emp++;
        int idx = 0; while(idx<n and (idx==emp or is_mono(idx)) ) idx++;
        if(idx==n) break;
        move(idx,emp); char want = stacks[emp][0];
        int spot1 = idx;
        if(stacks[spot1].back() == want){
            move(spot1,emp);
            if(stacks[spot1].back() == want){
                move(spot1,emp);
            } else{ //go find the third one, in this case spot1 has 2 free so its very easy
                int idx2 = 0; while(idx2 == emp or idx2==spot1 or !has(stacks[idx2],want)) idx2++; 
                while(stacks[idx2].back() != want) move(idx2,spot1);
                move(idx2,emp); //great
            }
        } else{ //go find the second one
            int idx2 = 0; while(idx2 == emp or idx2==spot1 or !has(stacks[idx2],want)) idx2++; 
            
            //dig
            while(stacks[idx2].back() != want) move(idx2,emp);
            move(idx2,spot1);
            while(stacks[emp].back() != want) move(emp,idx2);
            move(spot1,emp);
            int spot2 = idx2;

            //spot1 has 1 free, spot2 has 1 free
            //either its 1 deep in spot1 or spot2
            //or its somewhere else
            int idx3 = 0; while(idx3 == emp or !has(stacks[idx3],want)) idx3++;
            if(idx3 == spot1 or idx3 == spot2){
                if(idx3 != spot1) swap(spot1,spot2); //it is one deep at spot1 now
                move(spot1,spot2);
                move(spot1,emp); //incredible work
            }else{
                if(stacks[idx3].back() != want) move(idx3,spot1);
                if(stacks[idx3].back() != want) move(idx3,spot2);
                move(idx3,emp); //done
            }
        }
    }

    cout << len(ans) << '\n';
    for(auto [u,v] : ans) cout << u+1 << " " << v+1 << '\n';

    // for(auto &v : stacks){
    //     ranges::copy(v,oit<ll>()),cout<<endl;
    //     cout << "-----------\n";
    // }
}

int main()
{
    //KING OF THE WORLD...... U.W.T.B
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    run();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3844kb

input:

3
2 2 0
1 3 1
3 1 2
3 0 0

output:

18
1 4
1 4
2 1
3 1
3 2
1 3
2 1
2 3
2 1
3 2
4 2
4 2
4 3
2 4
2 4
3 2
3 4
3 2

result:

ok correct

Test #2:

score: 0
Accepted
time: 0ms
memory: 3800kb

input:

1
0 0 0
1 1 1

output:

0

result:

ok correct

Test #3:

score: -100
Runtime Error

input:

2
2 1 0
2 1 0
2 1 0

output:


result: