QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#719596 | #5583. Color Tubes | nickbelov# | TL | 0ms | 3776kb | C++20 | 4.8kb | 2024-11-07 04:41:51 | 2024-11-07 04:41:52 |
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)<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: 3776kb
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: -100
Time Limit Exceeded
input:
1 0 0 0 1 1 1