Skip to content

Instantly share code, notes, and snippets.

@farma11 farma11/AOJ0033_Bit01.cpp
Last active Feb 5, 2018

Embed
What would you like to do?
#include <iostream>
using namespace std;
int main() {
int n, balls[10]; cin >> n;
while(n--){
for(int i = 0; i < 10; i++) cin >> balls[i];
bool sortable = false;
for(int i = 0; i < (1 << 10); i++){
int bit = i;
bool ok = true;
int top[2] = {0,0}; //top[0]: B, top[1]: C
for(int j = 0; j < 10; j++){
if(top[bit & 1] > balls[j]){
ok = false; break;
}
top[bit & 1] = balls[j];
bit >>= 1;
}
if(ok) {
sortable = true; break;
}
}
cout << (sortable ? "YES" : "NO") << endl;
}
}
#include <iostream>
using namespace std;
int balls[10]; // 玉の順序を記録
bool dfs(int idx, int b, int c){
if(idx > 9) return true;
bool ok = false;
if(b < balls[idx]){
ok = dfs(idx+1, balls[idx], c); // 筒Bに入れられるとき
}
if(c < balls[idx]){
ok = dfs(idx+1, b, balls[idx]); // 筒Cに入れられるとき
}
return ok;
}
int main() {
int n; cin >> n; // データセットの数
while(n--){
for(int i = 0; i < 10; i++) cin >> balls[i];
cout << (dfs(0, 0, 0) ? "YES" : "NO") << endl;
}
}
#include <iostream>
#include <stack>
#include <tuple>
using namespace std;
int main() {
int n; cin >> n;
while(n--){
int balls[10];
for(int i = 0; i < 10; i++) cin >> balls[i];
enum {IDX, B, C};
stack<tuple<int, int, int> > states;
bool sortable = false;
states.push(make_tuple(0,0,0));
while(!states.empty()){
tuple<int, int, int> now = states.top();
states.pop();
int idx = get<IDX>(now);
if(idx < 10){
if(get<B>(now) < balls[idx]){
if(idx == 9){
sortable = true; break;
}
states.push(make_tuple(idx+1,balls[idx],get<C>(now)));
}
if(get<C>(now) < balls[idx]){
if(idx == 9){
sortable = true; break;
}
states.push(make_tuple(idx+1,get<B>(now),balls[idx]));
}
}
}
cout << (sortable ? "YES" : "NO") << endl;
}
}
#include <iostream>
using namespace std;
int main() {
int n; cin >> n; // データセットの数
while(n--){
int balls[10] = {0};
for(int i = 0; i < 10; i++) cin >> balls[i]; // 各データセットの入力
bool isYES = true; // 玉10個を振り分けられるかどうか
int topB = 0, topC = 0; // 筒B及び筒Cの最上部の玉の値
for(int i = 0; i < 10; i++){
if (topB < balls[i]){
topB = balls[i];
} else if (topC < balls[i]) {
topC = balls[i];
} else {
isYES = false;
break;
}
}
cout << (isYES ? "YES" : "NO") << endl;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.