QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#378682#8566. Can We Still Qualify For Semifinals?ucup-team133#AC ✓7ms3868kbC++179.0kb2024-04-06 14:10:222024-04-06 14:10:23

Judging History

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

  • [2024-04-06 14:10:23]
  • 评测
  • 测评结果:AC
  • 用时:7ms
  • 内存:3868kb
  • [2024-04-06 14:10:22]
  • 提交

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