fork(1) download 
  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <stack>
  4. #include <queue>
  5. #include <deque>
  6. #include <vector>
  7. #include <string>
  8. #include <string.h>
  9. #include <cstdlib>
  10. #include <ctime>
  11. #include <cmath>
  12. #include <map>
  13. #include <set>
  14. #include <iostream>
  15. #include <sstream>
  16. #include <numeric>
  17. #include <cctype>
  18. #include <bitset>
  19. #include <cassert>
  20. #define fi first
  21. #define se second
  22. #define rep(i,n) for(int i = 0; i < (n); ++i)
  23. #define rrep(i,n) for(int i = 1; i <= (n); ++i)
  24. #define drep(i,n) for(int i = (n)-1; i >= 0; --i)
  25. #define gep(i,g,j) for(int i = g.head[j]; i != -1; i = g.e[i].next)
  26. #define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
  27. #define rng(a) a.begin(),a.end()
  28. #define maxs(x,y) x = max(x,y)
  29. #define mins(x,y) x = min(x,y)
  30. #define pb push_back
  31. #define sz(x) (int)(x).size()
  32. #define pcnt __builtin_popcount
  33. #define uni(x) x.erase(unique(rng(x)),x.end())
  34. #define snuke srand((unsigned)clock()+(unsigned)time(NULL));
  35. #define df(x) int x = in()
  36. #define dame { puts("-1"); return 0;}
  37. #define show(x) cout<<#x<<" = "<<x<<endl;
  38. #define PQ(T) priority_queue<T,vector<T>,greater<T> >
  39. #define bn(x) ((1<<x)-1)
  40. #define newline puts("")
  41. #define v(T) vector<T>
  42. #define vv(T) vector<vector<T>>
  43. using namespace std;
  44. typedef long long int ll;
  45. typedef unsigned uint;
  46. typedef unsigned long long ull;
  47. typedef pair<int,int> P;
  48. typedef vector<int> vi;
  49. typedef vector<vi> vvi;
  50. typedef vector<ll> vl;
  51. typedef vector<P> vp;
  52. inline int in() { int x; scanf("%d",&x); return x;}
  53. inline void priv(vi a) { rep(i,sz(a)) printf("%d%c",a[i],i==sz(a)-1?'\n':' ');}
  54. template<typename T>istream& operator>>(istream&i,vector<T>&v)
  55. {rep(j,sz(v))i>>v[j];return i;}
  56. template<typename T>string join(const vector<T>&v)
  57. {stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
  58. template<typename T>ostream& operator<<(ostream&o,const vector<T>&v)
  59. {if(sz(v))o<<join(v);return o;}
  60. template<typename T1,typename T2>istream& operator>>(istream&i,pair<T1,T2>&v)
  61. {return i>>v.fi>>v.se;}
  62. template<typename T1,typename T2>ostream& operator<<(ostream&o,const pair<T1,T2>&v)
  63. {return o<<v.fi<<","<<v.se;}
  64. const int MX = 100005, INF = 1001001001;
  65. const ll LINF = 1e18;
  66. const double eps = 1e-10;
  67.  
  68. // Max flow
  69. // !! Be care of double and INF !!
  70. struct Maxflow {
  71.   typedef int TT;
  72.   int n;
  73.   vi to, next, head, dist, it;
  74.   vector<TT> lim;
  75.   Maxflow(){}
  76.   Maxflow(int n):n(n),head(n,-1),it(n){}
  77.   void add(int a, int b, TT c=1) {
  78.     next.pb(head[a]); head[a] = sz(to); to.pb(b); lim.pb(c);
  79.     next.pb(head[b]); head[b] = sz(to); to.pb(a); lim.pb(0); 
  80.   }
  81.   void bfs(int sv) {
  82.     dist = vi(n,INF); // INF !!
  83.     queue<int> q;
  84.     dist[sv] = 0; q.push(sv);
  85.     while (!q.empty()){
  86.       int v = q.front(); q.pop();
  87.       for (int i = head[v]; i != -1; i = next[i]) {
  88.         if (lim[i] && dist[to[i]] == INF) { // double INF !!
  89.           dist[to[i]] = dist[v]+1; q.push(to[i]);
  90.         }
  91.       }
  92.     }
  93.   }
  94.   TT dfs(int v, int tv, TT nf=INF) { // INF !!
  95.     if (v == tv) return nf;
  96.     for (; it[v] != -1; it[v] = next[it[v]]) {
  97.       int u = to[it[v]]; TT f;
  98.       if (!lim[it[v]] || dist[v] >= dist[u]) continue;
  99.       if (f = dfs(u, tv, min(nf, lim[it[v]])), f) { // double !!
  100.         lim[it[v]] -= f;
  101.         lim[it[v]^1] += f;
  102.         return f;
  103.       }
  104.     }
  105.     return 0;
  106.   }
  107.   int solve(int sv, int tv) {
  108.     TT flow = 0, f;
  109.     while (1) {
  110.       bfs(sv);
  111.       if (dist[tv] == INF) return flow; // INF !!
  112.       rep(i,n) it[i] = head[i];
  113.       while (f = dfs(sv,tv), f) flow += f;
  114.     }
  115.   }
  116. };
  117. //
  118.  
  119. int read() {
  120.   char c;
  121.   cin>>c;
  122.   if (c == '-') return -1;
  123.   if (c == '*') return -2;
  124.   return c-'A';
  125. }
  126.  
  127. const int hands[] = {5,5,4,4};
  128. const int cards[] = {6,6,9};
  129.  
  130. int n;
  131. vvi suggest;
  132. vvi clue;
  133.  
  134. vi hand;
  135. vvi can;
  136.  
  137. void solve(vi distribution) {
  138.   vi now;
  139.   rep(i,12) if (distribution[i] == 4) now.pb(i);
  140.   if (sz(now) != 2) return;
  141.  
  142.   vvi table(5,vi(9));
  143.   bool ok = true;
  144.   auto add = [&](int i, int j, int x) {
  145.     if (j < 12) {
  146.       if ((distribution[j] == i) != (x == 1)) ok = false;
  147.       return;
  148.     }
  149.     j -= 12;
  150.     if (table[i][j] && table[i][j] != x) {
  151.       ok = false;
  152.       return;
  153.     }
  154.     table[i][j] = x;
  155.   };
  156.  
  157.   rep(i,5) add(0,hand[i],1);
  158.  
  159.   rep(i,n) {
  160.     rep(j,sz(clue[i])) {
  161.       if (clue[i][j] != -1) break;
  162.       int ni = (i+j+1)%4;
  163.       rep(k,3) add(ni,suggest[i][k],-1);
  164.     }
  165.  
  166.     int ni = (i+sz(clue[i]))%4;
  167.     if (clue[i].back() == -2) {
  168.       bool has = false;
  169.       rep(k,2) {
  170.         if (distribution[suggest[i][k]] == ni) has = true;
  171.       }
  172.       if (!has) add(ni,suggest[i][2],1);
  173.     } else if (clue[i].back() != -1) {
  174.       add(ni,clue[i].back(),1);
  175.     }
  176.   }
  177.  
  178.   if (!ok) return;
  179.  
  180.   rep(j,9) {
  181.     int cnt = 0;
  182.     rep(i,5) if (table[i][j] == 1) cnt++;
  183.     if (cnt > 1) return;
  184.     if (cnt == 1) {
  185.       rep(i,5) if (table[i][j] != 1) table[i][j] = -1;
  186.     }
  187.   }
  188.  
  189.   now.pb(-1);
  190.   for (int room = 12; room < 21; ++room) {
  191.     if (table[4][room-12] == -1) continue;
  192.     int sv = 4+9, tv = sv+1;
  193.     Maxflow g(tv+1);
  194.     rep(i,4) rep(j,9) {
  195.       if (table[i][j] != -1) g.add(i,j+4);
  196.     }
  197.     vi cnt(5);
  198.     rep(j,12) cnt[distribution[j]]++;
  199.     rep(i,4) g.add(sv,i,hands[i]-cnt[i]);
  200.     rep(j,9) if (room != j+12) g.add(j+4,tv);
  201.  
  202.     now.back() = room;
  203.     if (g.solve(sv,tv) == 9-1) {
  204.       can.pb(now);
  205.     }
  206.   }
  207. }
  208.  
  209. bool fineRemoved(vi distribution) {
  210.   rep(i,2) {
  211.     int cnt = 0, cnt2 = 0;
  212.     for (int j = 6*i; j < 6*i+6; ++j) {
  213.       if (j < sz(distribution) && distribution[j] == 4) cnt++, cnt2++;
  214.       if (j >= sz(distribution)) cnt2++;
  215.     }
  216.     if (cnt > 1) return false;
  217.     if (!cnt2) return false;
  218.   }
  219.   return true;
  220. }
  221. bool fineHands(vi distribution) {
  222.   vi cnt(5);
  223.   rep(i,sz(distribution)) cnt[distribution[i]]++;
  224.   rep(i,4) if (cnt[i] > hands[i]) return false;
  225.   return true;
  226. }
  227. void dfs(vi distribution) {
  228.   if (!fineRemoved(distribution)) return;
  229.   if (!fineHands(distribution)) return;
  230.   if (sz(distribution) == 12) {
  231.     solve(distribution);
  232.     return;
  233.   }
  234.   distribution.pb(0);
  235.   if (find(rng(hand),sz(distribution)-1) != hand.end()) {
  236.     dfs(distribution);
  237.   } else {
  238.     rep(i,4) {
  239.       distribution.back()++;
  240.       dfs(distribution);
  241.     }
  242.   }
  243. }
  244.  
  245. int main() {
  246.   cin>>n;
  247.   hand = vi(5);
  248.   rep(i,5) hand[i] = read();
  249.   suggest = vvi(n,vi(3));
  250.   clue = vvi(n);
  251.   rep(i,n) {
  252.     rep(j,3) suggest[i][j] = read();
  253.     rep(j,3) {
  254.       clue[i].pb(read());
  255.       if (clue[i].back() != -1) break;
  256.     }
  257.   }
  258.  
  259.   dfs(vi());
  260.  
  261.   string ans;
  262.   rep(i,3) {
  263.     vi a;
  264.     rep(j,sz(can)) a.pb(can[j][i]);
  265.     assert(sz(a));
  266.     sort(rng(a)); uni(a);
  267.     if (sz(a) == 1) ans += 'A'+a[0];
  268.     else ans += '?';
  269.   }
  270.   cout<<ans<<endl;
  271.   return 0;
  272. }
  273.  
  274.  
Success #stdin #stdout 3.47s 47184KB
comments (?)
stdin 
50
M N O P Q
A G O A
A G O - - O
A G O - O
A G O O
A G O A
A G O - - O
A G O - O
A G O O
A G O A
A G O - - O
A G O - O
A G O O
A G O A
A G O - - O
A G O - O
A G O O
A G O A
A G O - - O
A G O - O
A G O O
A G O A
A G O - - O
A G O - O
A G O O
A G O A
A G O - - O
A G O - O
A G O O
A G O A
A G O - - O
A G O - O
A G O O
A G O A
A G O - - O
A G O - O
A G O O
A G O A
A G O - - O
A G O - O
A G O O
A G O A
A G O - - O
A G O - O
A G O O
A G O A
A G O - - O
A G O - O
A G O O
A G O A
A G O - - O
stdout 
???
https://ideone.com/vf9UCC
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!