QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#378682 | #8566. Can We Still Qualify For Semifinals? | ucup-team133# | AC ✓ | 7ms | 3868kb | C++17 | 9.0kb | 2024-04-06 14:10:22 | 2024-04-06 14:10:23 |
Judging History
answer
// -fsanitize=undefined,
//#define _GLIBCXX_DEBUG
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <random>
#include <stdio.h>
#include <fstream>
#include <functional>
#include <cassert>
#include <unordered_map>
#include <bitset>
#include <chrono>
#include <algorithm>
#include <vector>
namespace atcoder {
namespace internal {
template <class T> struct simple_queue {
std::vector<T> payload;
int pos = 0;
void reserve(int n) { payload.reserve(n); }
int size() const { return int(payload.size()) - pos; }
bool empty() const { return pos == int(payload.size()); }
void push(const T& t) { payload.push_back(t); }
T& front() { return payload[pos]; }
void clear() {
payload.clear();
pos = 0;
}
void pop() { pos++; }
};
} // namespace internal
} // namespace atcoder
#include <cassert>
#include <limits>
#include <queue>
#include <vector>
namespace atcoder {
template <class Cap> struct mf_graph {
public:
mf_graph() : _n(0) {}
mf_graph(int n) : _n(n), g(n) {}
int add_edge(int from, int to, Cap cap) {
assert(0 <= from && from < _n);
assert(0 <= to && to < _n);
assert(0 <= cap);
int m = int(pos.size());
pos.push_back({from, int(g[from].size())});
int from_id = int(g[from].size());
int to_id = int(g[to].size());
if (from == to) to_id++;
g[from].push_back(_edge{to, to_id, cap});
g[to].push_back(_edge{from, from_id, 0});
return m;
}
struct edge {
int from, to;
Cap cap, flow;
};
edge get_edge(int i) {
int m = int(pos.size());
assert(0 <= i && i < m);
auto _e = g[pos[i].first][pos[i].second];
auto _re = g[_e.to][_e.rev];
return edge{pos[i].first, _e.to, _e.cap + _re.cap, _re.cap};
}
std::vector<edge> edges() {
int m = int(pos.size());
std::vector<edge> result;
for (int i = 0; i < m; i++) {
result.push_back(get_edge(i));
}
return result;
}
void change_edge(int i, Cap new_cap, Cap new_flow) {
int m = int(pos.size());
assert(0 <= i && i < m);
assert(0 <= new_flow && new_flow <= new_cap);
auto& _e = g[pos[i].first][pos[i].second];
auto& _re = g[_e.to][_e.rev];
_e.cap = new_cap - new_flow;
_re.cap = new_flow;
}
Cap flow(int s, int t) {
return flow(s, t, std::numeric_limits<Cap>::max());
}
Cap flow(int s, int t, Cap flow_limit) {
assert(0 <= s && s < _n);
assert(0 <= t && t < _n);
assert(s != t);
std::vector<int> level(_n), iter(_n);
internal::simple_queue<int> que;
auto bfs = [&]() {
std::fill(level.begin(), level.end(), -1);
level[s] = 0;
que.clear();
que.push(s);
while (!que.empty()) {
int v = que.front();
que.pop();
for (auto e : g[v]) {
if (e.cap == 0 || level[e.to] >= 0) continue;
level[e.to] = level[v] + 1;
if (e.to == t) return;
que.push(e.to);
}
}
};
auto dfs = [&](auto self, int v, Cap up) {
if (v == s) return up;
Cap res = 0;
int level_v = level[v];
for (int& i = iter[v]; i < int(g[v].size()); i++) {
_edge& e = g[v][i];
if (level_v <= level[e.to] || g[e.to][e.rev].cap == 0) continue;
Cap d =
self(self, e.to, std::min(up - res, g[e.to][e.rev].cap));
if (d <= 0) continue;
g[v][i].cap += d;
g[e.to][e.rev].cap -= d;
res += d;
if (res == up) break;
}
return res;
};
Cap flow = 0;
while (flow < flow_limit) {
bfs();
if (level[t] == -1) break;
std::fill(iter.begin(), iter.end(), 0);
while (flow < flow_limit) {
Cap f = dfs(dfs, t, flow_limit - flow);
if (!f) break;
flow += f;
}
}
return flow;
}
std::vector<bool> min_cut(int s) {
std::vector<bool> visited(_n);
internal::simple_queue<int> que;
que.push(s);
while (!que.empty()) {
int p = que.front();
que.pop();
visited[p] = true;
for (auto e : g[p]) {
if (e.cap && !visited[e.to]) {
visited[e.to] = true;
que.push(e.to);
}
}
}
return visited;
}
private:
int _n;
struct _edge {
int to, rev;
Cap cap;
};
std::vector<std::pair<int, int>> pos;
std::vector<std::vector<_edge>> g;
};
} // namespace atcoder
using namespace std;
using namespace atcoder;
#define rep(i,n) for (int i=0;i<n;i+=1)
#define rrep(i,n) for (int i=n-1;i>-1;i--)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << " )\n";
template<class T>
using vec = vector<T>;
template<class T>
using vvec = vec<vec<T>>;
template<class T>
using vvvec = vec<vvec<T>>;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<class T>
bool chmin(T &a, T b){
if (a>b){
a = b;
return true;
}
return false;
}
template<class T>
bool chmax(T &a, T b){
if (a<b){
a = b;
return true;
}
return false;
}
template<class T>
T sum(vec<T> x){
T res=0;
for (auto e:x){
res += e;
}
return res;
}
template<class T>
void printv(vec<T> x){
for (auto e:x){
cout<<e<<" ";
}
cout<<endl;
}
template<class T,class U>
ostream& operator<<(ostream& os, const pair<T,U>& A){
os << "(" << A.first <<", " << A.second << ")";
return os;
}
template<class T>
ostream& operator<<(ostream& os, const set<T>& S){
os << "set{";
for (auto a:S){
os << a;
auto it = S.find(a);
it++;
if (it!=S.end()){
os << ", ";
}
}
os << "}";
return os;
}
template<class T>
ostream& operator<<(ostream& os, const tuple<T,T,T>& a){
auto [x,y,z] = a;
os << "(" << x << ", " << y << ", " << z << ")";
return os;
}
template<class T>
ostream& operator<<(ostream& os, const map<int,T>& A){
os << "map{";
for (auto e:A){
os << e.first;
os << ":";
os << e.second;
os << ", ";
}
os << "}";
return os;
}
template<class T>
ostream& operator<<(ostream& os, const vec<T>& A){
os << "[";
rep(i,A.size()){
os << A[i];
if (i!=A.size()-1){
os << ", ";
}
}
os << "]" ;
return os;
}
void solve(){
int N = 10;
vector<pii> match;
vector<int> tmp = {0,1,2,3,4,5,6,7,8,9};
rep(_,9){
rep(i,5){
match.push_back({tmp[i],tmp[N-1-i]});
}
vec<int> nxt_tmp = {0,tmp.back()};
for (int i=1;i<9;i++){
nxt_tmp.push_back(tmp[i]);
}
swap(tmp,nxt_tmp);
}
int K;
cin>>K;
string S;
cin>>S;
vec<vec<int>> tmp_res(N,vec<int>(N,-1));
rep(i,K){
auto [x,y] = match[i];
if (S[i] == '1'){
tmp_res[x][y] = 1;
tmp_res[y][x] = 0;
}
else{
tmp_res[y][x] = 1;
tmp_res[x][y] = 0;
}
}
int ind_win = 0;
rep(y,N){
if (y == 0) continue;
if (tmp_res[0][y] == -1){
tmp_res[0][y] = 1;
tmp_res[y][0] = 0;
}
ind_win += tmp_res[0][y];
}
string ans = "NO";
for (int i=1;i<N;i++){
for (int j=i+1;j<N;j++){
for (int k=j+1;k<N;k++){
mf_graph<int> G(N*(N-1)/2 + N + 2);
int S = N*(N-1)/2+N, T = N*(N-1)/2+N+1;
int match_cnt = N*(N-1)/2;
rep(m,match_cnt){
G.add_edge(S,m,1);
auto [x,y] = match[m];
if (tmp_res[x][y] == -1){
G.add_edge(m,match_cnt+x,1);
G.add_edge(m,match_cnt+y,1);
}
else if (tmp_res[x][y] == 1){
G.add_edge(m,match_cnt+x,1);
}
else{
G.add_edge(m,match_cnt+y,1);
}
}
rep(t,N){
if (t == i || t == j || t== k){
G.add_edge(t+match_cnt,T,N);
}
else{
G.add_edge(t+match_cnt,T,ind_win);
}
}
int check = G.flow(S,T);
if (check == match_cnt){
ans = "YES";
}
}
}
}
cout << ans << "\n";
}
int main(){
int T;
cin>>T;
while (T--){
solve();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 3628kb
input:
3 3 111 25 1000010101111111111010100 35 01111011110111101111011110111101111
output:
YES YES NO
result:
ok 3 token(s): yes count is 2, no count is 1
Test #2:
score: 0
Accepted
time: 6ms
memory: 3868kb
input:
10 16 0110000001010100 17 01111000110110101 15 001100010101111 16 0010101010011100 19 0000000100010110100 16 0011101010011100 18 011110010001100000 18 000110101001100011 20 01100010000100100100 15 001000111001101
output:
YES YES YES YES YES YES YES YES YES YES
result:
ok 10 token(s): yes count is 10, no count is 0
Test #3:
score: 0
Accepted
time: 6ms
memory: 3636kb
input:
10 37 0110000001010100011101001011100110001 39 000100111101101001100101101000000000100 35 00111000100111100101011010111100100 33 010000010001110010110001101110001 30 000100010100000010010110101010 31 0000101000011010101001010000000 44 00001000000111101011010110000101100011000100 42 01111011110001001...
output:
NO NO NO NO NO NO NO NO NO NO
result:
ok 10 token(s): yes count is 0, no count is 10
Test #4:
score: 0
Accepted
time: 6ms
memory: 3832kb
input:
10 23 01100000010101000111010 38 01111001100011000101011110101001101001 27 010000000001001001110001001 26 01101001110011101101000110 8 00001000 22 0110100110001110110001 9 000100010 24 000000100101101010100100 6 011000 29 01101010100101000000000000100
output:
YES NO NO NO YES YES YES YES YES NO
result:
ok 10 token(s): yes count is 6, no count is 4
Test #5:
score: 0
Accepted
time: 6ms
memory: 3628kb
input:
10 30 011000000101010001110100101110 29 01001010010011101110010110010 28 0110000000001000101101001001 23 01101001110011101101000 23 01000001000111001011000 24 011110001000010001010000 23 01001011010101001000011 30 000110011001010010000000000010 24 000110111001110011000011 28 000110001000011011110110...
output:
NO NO NO YES YES YES YES NO YES NO
result:
ok 10 token(s): yes count is 5, no count is 5
Test #6:
score: 0
Accepted
time: 6ms
memory: 3624kb
input:
10 21 011000000101010001110 21 000110110101001010010 22 0111101101001100101101 24 000000001000101011000101 21 011010011100111011010 20 00110000010001101010 21 010010111100010000100 24 010100000100011010110010 23 00001010000110101010010 25 0000000000001000001101110
output:
YES YES YES YES YES YES YES YES YES YES
result:
ok 10 token(s): yes count is 10, no count is 0
Test #7:
score: 0
Accepted
time: 6ms
memory: 3528kb
input:
10 26 01100000010101000111010010 26 01101010010100100111011100 26 00110010110100000000010010 27 011100010101110010110101101 30 010100011000001000110101001100 30 011110001000010001010000001001 28 0101100101000010100001101010 26 00101000000000000100000110 28 0110101101010000111000110001 27 00011011110...
output:
NO NO NO NO NO NO NO NO NO NO
result:
ok 10 token(s): yes count is 0, no count is 10
Test #8:
score: 0
Accepted
time: 6ms
memory: 3860kb
input:
10 25 0010100010011010111001111 26 01001010100010101010001010 26 01111001110000100111011110 26 10001000100110101110011110 26 10101010100110101110011110 27 110100010101010011010111001 27 101010101001101011100111101 31 1000010001010100110001011011110 37 1000101111000100110000011000000100101 40 1000101...
output:
NO NO NO NO NO NO NO NO NO NO
result:
ok 10 token(s): yes count is 0, no count is 10
Test #9:
score: 0
Accepted
time: 7ms
memory: 3792kb
input:
10 26 00001010000000000000000000 26 00000010000000000000000000 26 01101010100010101011011110 26 00011011110111101111011110 27 001100110101011001110111101 27 000110111101111011110111101 28 0110001001000010011101111011 29 01000000010001101000011110111 29 01000000010000101101011110111 30 01000011110111...
output:
YES YES YES YES YES YES YES YES YES NO
result:
ok 10 token(s): yes count is 9, no count is 1
Test #10:
score: 0
Accepted
time: 6ms
memory: 3580kb
input:
10 1 0 2 00 10 0001101110 14 00101010000011 20 00000010010100101010 25 0000000101000100100001111 35 01110011010000101010000010010000100 40 0000100110001110101100001001000110000001 44 01011010110010101110011000010001010011100011 45 010010001001010011110111101011011000000100001
output:
YES YES YES YES YES YES NO NO NO NO
result:
ok 10 token(s): yes count is 6, no count is 4
Extra Test:
score: 0
Extra Test Passed