fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <sstream>
  5. #include <map>
  6. #include <queue>
  7. using namespace std;
  8.  
  9. #define LL long long
  10.  
  11. template<class T>
  12. T C(T a, char op, T b) {
  13.     if (op=='+') return a + b;
  14.     if (op=='-') return a - b;
  15.     if (op=='*') return a * b;
  16.     throw 0;
  17. }
  18.  
  19. template<class T, class P>
  20. string V(T a, char op, P b) {
  21.     stringstream ss;
  22.     ss << '(' << a << op << b << ')';
  23.     return string(ss.str());
  24. }
  25.  
  26. vector<int> ke[2000];
  27. int trace[2000];
  28.  
  29. int match(int n, int m) {
  30.     vector<int> visited(n, -1);
  31.     vector<int> ref(n);
  32.  
  33.     vector<int> mx(n, -1);
  34.     vector<int> my(m, -1);
  35.     int cnt = 0;
  36.  
  37.     for (int i=0; i<n; i++) if (mx[i] < 0) {
  38.         struct { int u, v; } res = {-1, -1};
  39.  
  40.         queue<int> q;
  41.         q.push(i);
  42.         visited[i] = i;
  43.         while (!q.empty()) {
  44.             int u = q.front(); q.pop();
  45.             for (int v: ke[u]) {
  46.                 if (my[v] >= 0 && visited[my[v]] != i) {
  47.                     q.push(my[v]);
  48.                     ref[my[v]] = u;
  49.                     visited[my[v]] = i;
  50.                 } else if (my[v] < 0) {
  51.                     res = {u, v}; 
  52.                     break;
  53.                 }
  54.             }
  55.             if (res.u >= 0) break;
  56.         }
  57.  
  58.         if (res.u >= 0) {
  59.             cnt++;
  60.             while (true) {
  61.                 int vv = mx[res.u];
  62.                 mx[res.u] = res.v;
  63.                 my[res.v] = res.u;
  64.                 if (res.u == i) break;
  65.                 res = {ref[res.u], vv};
  66.             };
  67.         }
  68.     }
  69.  
  70.     if (cnt < n) return cnt;
  71.  
  72.     for (int i=0; i<n; i++) if (mx[i] >= 0) {
  73.         for (int j=0; j<(int)ke[i].size(); j++) {
  74.             if (ke[i][j] == mx[i]) {
  75.                 trace[i] = j;
  76.                 break;
  77.             }
  78.         }
  79.     } else trace[i] = -1;
  80.  
  81.     return cnt;
  82. }
  83.  
  84. int main() {
  85.     ios::sync_with_stdio(false); cin.tie(0);
  86.     int n; cin >> n; cin.ignore();
  87.     vector<vector<string>> view(n);
  88.     vector<vector<LL>> val(n);
  89.     for (int i=0; i<n; i++) {
  90.         string s;
  91.         getline(cin, s);
  92.  
  93.         int cnt_op = 0;
  94.         LL num[4] = {0,0,0,0};
  95.         char op[4];
  96.         for (char c: s) {
  97.             if ('0' <= c && c <= '9') {
  98.                 num[cnt_op] *= 10;
  99.                 num[cnt_op] += c - '0';
  100.             } else {
  101.                 op[cnt_op] = c;
  102.                 cnt_op++;
  103.             }
  104.         }
  105.  
  106.         if (cnt_op == 1) {
  107.             val[i].push_back(C(num[0], op[0], num[1]));
  108.             view[i].push_back(s);
  109.         }
  110.         if (cnt_op == 2) {
  111.             val[i].push_back(C(C(num[0],op[0],num[1]),op[1],num[2]));
  112.             val[i].push_back(C(num[0],op[0],C(num[1],op[1],num[2])));
  113.             view[i].push_back(V(V(num[0],op[0],num[1]),op[1],num[2]));
  114.             view[i].push_back(V(num[0],op[0],V(num[1],op[1],num[2])));
  115.         }
  116.         if (cnt_op == 3) {
  117.             val[i].push_back(C(C(C(num[0],op[0],num[1]),op[1],num[2]),op[2],num[3])); // 0 1 2
  118.             val[i].push_back(C(C(num[0],op[0],num[1]),op[1],C(num[2],op[2],num[3]))); // 0 2 1
  119.             val[i].push_back(C(C(num[0],op[0],C(num[1],op[1],num[2])),op[2],num[3])); // 1 0 2
  120.             val[i].push_back(C(num[0],op[0],C(C(num[1],op[1],num[2]),op[2],num[3]))); // 1 2 0
  121.             val[i].push_back(C(num[0],op[0],C(num[1],op[1],C(num[2],op[2],num[3])))); // 2 1 0
  122.             view[i].push_back(V(V(V(num[0],op[0],num[1]),op[1],num[2]),op[2],num[3])); // 0 1 2
  123.             view[i].push_back(V(V(num[0],op[0],num[1]),op[1],V(num[2],op[2],num[3]))); // 0 2 1
  124.             view[i].push_back(V(V(num[0],op[0],V(num[1],op[1],num[2])),op[2],num[3])); // 1 0 2
  125.             view[i].push_back(V(num[0],op[0],V(V(num[1],op[1],num[2]),op[2],num[3]))); // 1 2 0
  126.             view[i].push_back(V(num[0],op[0],V(num[1],op[1],V(num[2],op[2],num[3])))); // 2 1 0
  127.         }
  128.  
  129.         /*
  130.         cout << s << endl;
  131.         for (int j=0; j<(int)ke[i].size(); j++) {
  132.             cout << "\t" << view[i][j] << '=' << ke[i][j] << endl;
  133.         }
  134.         */
  135.     }
  136.     map<LL, int> map;
  137.     for (int i=0; i<n; i++) {
  138.         for (LL v: val[i]) {
  139.             if (!map.count(v)) map.insert({v, (int)map.size()});
  140.             ke[i].push_back(map[v]);
  141.         }
  142.     }
  143.  
  144.     if ((int)map.size() < n) { cout << "NO SOLUTION"; return 0; }
  145.     int cnt = match(n, map.size());
  146.     if (cnt < n) { cout << "NO SOLUTION"; return 0; }
  147.     for (int i=0; i<n; i++) cout << view[i][trace[i]] << '\n';
  148.     return 0;
  149. }
  150.  
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/63KvUL
language:
C++ (gcc 8.3)
created:
11 days 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!