fork download
copy 
  1. // Mtaylor
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. #define pb push_back
  6. #define fi first
  7. #define se second
  8. #define mp make_pair
  9. #define endl '\n';
  10. #define sz(x) ((int)(x).size())
  11. #define all(x) (x).begin(), (x).end()
  12. #define rall(x) (x).rbegin(), (x).rend()
  13. void dbg_out() { cerr << endl; }
  14. template <typename Head, typename... Tail>
  15. void dbg_out(Head H, Tail... T) {
  16.     cerr << ' ' << H;
  17.     dbg_out(T...);
  18. }
  19. #define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
  20. typedef long long ll;
  21. const int N = 2505, E = 1e6, M = 3 * N;
  22.  
  23. #define neig(u, v, e) \
  24.     for (int e = head[u], v; (~e) && (v = to[e], 1); e = nxt[e])
  25. int head[N], nxt[E], to[E], edgcnt, n;
  26. int vis[N], vid = 0;
  27. int l2r[N], r2l[M];
  28.  
  29. void addEdge(int a, int b) {
  30.     nxt[edgcnt] = head[a];
  31.     head[a] = edgcnt;
  32.     to[edgcnt] = b;
  33.     edgcnt++;
  34. }
  35.  
  36. void init() {
  37.     memset(head, -1, n * sizeof(head[0]));
  38.     edgcnt = 0;
  39. }
  40.  
  41. int dfs(int lid) {
  42.     if (vis[lid] == vid) return 0;
  43.     vis[lid] = vid;
  44.     neig(lid, rid, e) {
  45.         if (r2l[rid] == -1 || dfs(r2l[rid])) {
  46.             r2l[rid] = lid;
  47.             l2r[lid] = rid;
  48.             return 1;
  49.         }
  50.     }
  51.     return 0;
  52. }
  53. int m, x, y;
  54. int maxMatching() {
  55.     int res = 0;
  56.     memset(r2l, -1, m * sizeof(r2l[0]));
  57.     for (int i = 0; i < n; i++) {
  58.         vid++;
  59.         res += dfs(i);
  60.     }
  61.     return res;
  62. }
  63. int val[N];
  64. set<ll> s;
  65. int a[N], b[N];
  66. map<ll, int> pos;
  67. vector<ll> distincts;
  68. void solve() {
  69.     cin >> n;
  70.     for (int i = 0; i < n; i++) {
  71.         cin >> a[i] >> b[i];
  72.         s.insert(a[i] + b[i]);
  73.         s.insert(a[i] - b[i]);
  74.         s.insert(a[i] * 1ll * b[i]);
  75.     }
  76.     m = 0;
  77.     for (auto u : s) {
  78.         distincts.pb(u);
  79.         pos[u] = m++;
  80.     }
  81.     init();
  82.     for (int i = 0; i < n; i++) {
  83.         cin >> a[i] >> b[i];
  84.         addEdge(i, pos[a[i] + b[i]]);
  85.         addEdge(i, pos[a[i] - b[i]]);
  86.         addEdge(i, pos[a[i] * 1ll * b[i]]);
  87.     }
  88.     int x = maxMatching();
  89.     if (x != n) {
  90.         cout << "impossible";
  91.         return;
  92.     }
  93.     for (int i = 0; i < n; i++) {
  94.         char op = '+';
  95.         ll v = distincts[l2r[i]];
  96.         if (v == a[i] - b[i]) {
  97.             op = '-';
  98.         } else if (v == a[i] * 1ll * b[i]) {
  99.             op = '*';
  100.         }
  101.         cout << a[i] << " " << op << " " << b[i] << " "
  102.              << "="
  103.              << " " << v << endl;
  104.     }
  105. }
  106.  
  107. int main() {
  108.     // freopen("input.txt", "r", stdin);
  109.     ios::sync_with_stdio(0);
  110.     cin.tie(0);
  111.     cout.tie(0);
  112.     int T;
  113.     // cin >>T;
  114.     T = 1;
  115.     while (T--) {
  116.         solve();
  117.     }
  118.     return 0;
  119. }
  120.  
Success #stdin #stdout 0s 5444KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/DxBEgf
language:
C++14 (gcc 8.3)
created:
1 year 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!