QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#719605#5583. Color Tubesnickbelov#RE 0ms3848kbC++204.8kb2024-11-07 04:51:012024-11-07 04:51:02

Judging History

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

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

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);
        if(len(ans) > 20 * (n)) assert(false);
    };
    auto is_mono = [&](int i){
        if(len(stacks[i])<3) return false;
        return stacks[i][0] == stacks[i][1] and stacks[i][1] == stacks[i][2];
    };


    auto has = [&](const vi &v, int want){
        return ranges::find(v,want)!=v.end();
    };

    while(true){

        int emp = 0; while(is_mono(emp)) emp++; //finds something we can make empty
        for(int i : rep(n)) if(i!=emp) //make it empty
            while(len(stacks[i])<3 and len(stacks[emp])>0) move(emp,i);        
        int idx = 0; while(idx<n and (idx==emp or is_mono(idx)) ) idx++; //find a bad tower
        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();
}

詳細信息

Test #1:

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

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: 3848kb

input:

1
0 0 0
1 1 1

output:

0

result:

ok correct

Test #3:

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

input:

2
2 1 0
2 1 0
2 1 0

output:

8
1 2
1 3
2 1
2 1
3 2
3 1
2 3
2 3

result:

ok correct

Test #4:

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

input:

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

output:

12
2 1
3 2
2 1
4 1
2 3
2 4
3 2
3 2
4 3
4 2
3 4
3 4

result:

ok correct

Test #5:

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

input:

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

output:

20
1 3
1 3
1 3
2 1
3 1
3 1
3 2
1 3
1 3
2 1
4 1
2 3
2 4
3 2
4 2
4 3
2 4
3 2
3 4
3 2

result:

ok correct

Test #6:

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

input:

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

output:

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

result:

ok correct

Test #7:

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

input:

6
0 0 0
1 2 3
1 2 3
1 2 3
4 5 6
4 5 6
4 5 6

output:

24
2 1
3 2
2 1
4 1
2 3
2 4
3 2
3 2
4 3
4 2
3 4
3 4
5 3
6 5
5 3
7 3
5 6
5 7
6 5
6 5
7 6
7 5
6 7
6 7

result:

ok correct

Test #8:

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

input:

6
0 0 0
1 5 6
1 2 6
1 2 3
4 2 3
4 5 3
4 5 6

output:

36
2 1
3 2
2 1
7 1
2 3
2 7
3 2
6 2
6 3
2 6
3 2
7 3
7 2
3 6
3 7
3 7
4 3
5 4
4 3
6 4
6 3
4 5
4 6
4 6
5 4
6 5
5 4
7 4
5 6
5 7
6 5
6 5
7 6
7 5
6 7
6 7

result:

ok correct

Test #9:

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

input:

9
1 2 3
4 5 6
7 8 9
1 2 3
4 5 6
7 8 9
1 2 3
4 5 6
7 8 9
0 0 0

output:

42
1 10
1 10
1 10
2 1
5 2
2 1
8 1
2 5
2 8
3 2
6 3
3 2
9 2
3 6
3 9
4 3
7 4
4 3
10 4
10 7
10 3
4 10
4 10
4 10
5 4
5 4
8 5
8 4
5 8
5 8
6 5
6 5
9 6
9 5
6 9
6 9
7 6
7 6
10 7
10 6
7 10
7 10

result:

ok correct

Test #10:

score: -100
Runtime Error

input:

10
1 2 3
4 5 6
7 8 9
10 1 2
3 4 5
6 7 8
9 10 1
2 3 4
5 6 7
8 9 10
0 0 0

output:


result: