QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#719602 | #5583. Color Tubes | nickbelov# | TL | 0ms | 3856kb | C++20 | 4.8kb | 2024-11-07 04:47:34 | 2024-11-07 04:47:35 |
Judging History
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){
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, char want){
for(char c : v) if(c==want) return true;
return false;
};
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: 3604kb
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: 3772kb
input:
1 0 0 0 1 1 1
output:
0
result:
ok correct
Test #3:
score: 0
Accepted
time: 0ms
memory: 3508kb
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: 3796kb
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: 3572kb
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: 3556kb
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: 3508kb
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: 3856kb
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: 3616kb
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
Time Limit Exceeded
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