Combothermal

Untitled

Oct 16th, 2019
241
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.66 KB | None | 0 0
  1. #pragma GCC optimize ("O3")
  2. #pragma GCC target ("sse4")
  3.  
  4. #include <bits/stdc++.h>
  5. #include <ext/pb_ds/tree_policy.hpp>
  6. #include <ext/pb_ds/assoc_container.hpp>
  7.  
  8. using namespace std;
  9. using namespace __gnu_pbds;
  10.  
  11. typedef long long ll;
  12. typedef long double ld;
  13. typedef complex<ld> cd;
  14.  
  15. typedef pair<int, int> pi;
  16. typedef pair<ll,ll> pl;
  17. typedef pair<ld,ld> pd;
  18.  
  19. typedef vector<int> vi;
  20. typedef vector<ld> vd;
  21. typedef vector<ll> vl;
  22. typedef vector<pi> vpi;
  23. typedef vector<pl> vpl;
  24. typedef vector<cd> vcd;
  25.  
  26. template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
  27.  
  28. #define FOR(i, a, b) for (int i=a; i<(b); i++)
  29. #define F0R(i, a) for (int i=0; i<(a); i++)
  30. #define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
  31. #define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
  32.  
  33. #define sz(x) (int)(x).size()
  34. #define mp make_pair
  35. #define pb push_back
  36. #define f first
  37. #define s second
  38. #define lb lower_bound
  39. #define ub upper_bound
  40. #define all(x) x.begin(), x.end()
  41. #define shandom_ruffle random_shuffle
  42.  
  43. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  44.  
  45. const int MOD = 1000000007;
  46. const ll INF = 1e18;
  47. const int MX = 100001; //check the limits, dummy
  48.  
  49. int decomp(int i, int N) {
  50. if (i == N-1) return N;
  51. if (i == N-2) return 1;
  52. return i+2;
  53. }
  54.  
  55. int main() {
  56. ios_base::sync_with_stdio(0); cin.tie(0);
  57.  
  58. int N; cin >> N;
  59. if (N == 2) {
  60. cout << "TAK" << endl;
  61. cout << "1 2 1" << endl;
  62. return 0;
  63. }
  64. int A[N-2], B[N-2]; F0R(i, N-2) cin >> A[i];
  65. F0R(i, N-2) cin >> B[i];
  66.  
  67. set<int> foundDifs;
  68. F0R(i, N-2) {
  69. foundDifs.insert(B[i] - A[i]);
  70. }
  71. if ((sz(foundDifs) == 1 && *foundDifs.begin() != 0) || (sz(foundDifs) == 2 && *foundDifs.begin() == -1 * *foundDifs.rbegin())) {
  72. cout << "TAK" << endl;
  73. int val = *foundDifs.begin();
  74. val = abs(val);
  75. cout << 1 << " " << N << " " << val << endl;
  76. F0R(i, N-2) {
  77. if (A[i] < B[i]) {
  78. cout << 1 << " " << i+2 << " " << A[i] << endl;
  79. } else {
  80. cout << N << " " << i+2 << " " << B[i] << endl;
  81. }
  82. }
  83. return 0;
  84. }
  85.  
  86.  
  87.  
  88. int loVal = 2000001;
  89. map<int, int> minima;
  90. set<int> minPos;
  91. bool bad = false;
  92. F0R(i, N-2) {
  93. if (A[i] + B[i] < loVal) {
  94. bad = false;
  95. minima.clear();
  96. minPos.clear();
  97. minPos.insert(i);
  98. loVal = A[i] + B[i];
  99. minima.insert(mp(A[i], i));
  100. } else if (A[i] + B[i] == loVal) {
  101. if (minima.count(A[i])) bad = true;
  102. minima.insert({A[i], i});
  103. minPos.insert(i);
  104. }
  105. }
  106.  
  107. if (bad) {
  108. cout << "NIE" << endl;
  109. return 0;
  110. }
  111.  
  112. vector<vpi> graph(N);
  113. graph[N-1].pb(mp(minima.rbegin()->s, loVal - minima.rbegin()->f));
  114. graph[N-2].pb(mp(minima.begin()->s, minima.begin()->f));
  115.  
  116. for (auto it = minima.begin(); it != minima.end(); it++) {
  117. auto it2 = minima.upper_bound(it->f);
  118. if (it2 == minima.end()) break;
  119. int A = it->f, B = it->s, C = it2->f, D = it2->s;
  120. graph[B].pb(mp(D, C-A));
  121. }
  122.  
  123. F0R(i, N-2) {
  124. if (minPos.count(i)) continue;
  125. int dif = A[i] - B[i];
  126. dif += loVal;
  127. if (dif % 2 == 1) {
  128. cout << "NIE" << endl; return 0;
  129. }
  130. dif /= 2;
  131. if (dif == 0) {
  132. graph[N-2].pb(mp(i, A[i]));
  133. } else if (dif == loVal) {
  134. graph[N-1].pb(mp(i, B[i]));
  135. } else if (minima.count(dif)) {
  136. int pos = minima[dif];
  137. graph[pos].pb(mp(i, A[i] - dif));
  138. } else {
  139. cout << "NIE" << endl; return 0;
  140. }
  141.  
  142. }
  143.  
  144. cout << "TAK" << endl;
  145. F0R(i, N) {
  146. F0R(j, sz(graph[i])) {
  147. cout << decomp(i, N) << " " << decomp(graph[i][j].f, N) << " " << graph[i][j].s << endl;
  148. }
  149. }
  150.  
  151.  
  152.  
  153. return 0;
  154. }
  155.  
  156. // read the question correctly (ll vs int)
  157. // template by bqi343
  158. // license: https://github.com/bqi343/USACO/blob/master/LICENSE
Advertisement
Add Comment
Please, Sign In to add comment