Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC optimize ("O3")
- #pragma GCC target ("sse4")
- #include <bits/stdc++.h>
- #include <ext/pb_ds/tree_policy.hpp>
- #include <ext/pb_ds/assoc_container.hpp>
- using namespace std;
- using namespace __gnu_pbds;
- typedef long long ll;
- typedef long double ld;
- typedef complex<ld> cd;
- typedef pair<int, int> pi;
- typedef pair<ll,ll> pl;
- typedef pair<ld,ld> pd;
- typedef vector<int> vi;
- typedef vector<ld> vd;
- typedef vector<ll> vl;
- typedef vector<pi> vpi;
- typedef vector<pl> vpl;
- typedef vector<cd> vcd;
- template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
- #define FOR(i, a, b) for (int i=a; i<(b); i++)
- #define F0R(i, a) for (int i=0; i<(a); i++)
- #define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
- #define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
- #define sz(x) (int)(x).size()
- #define mp make_pair
- #define pb push_back
- #define f first
- #define s second
- #define lb lower_bound
- #define ub upper_bound
- #define all(x) x.begin(), x.end()
- #define shandom_ruffle random_shuffle
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- const int MOD = 1000000007;
- const ll INF = 1e18;
- const int MX = 100001; //check the limits, dummy
- int decomp(int i, int N) {
- if (i == N-1) return N;
- if (i == N-2) return 1;
- return i+2;
- }
- int main() {
- ios_base::sync_with_stdio(0); cin.tie(0);
- int N; cin >> N;
- if (N == 2) {
- cout << "TAK" << endl;
- cout << "1 2 1" << endl;
- return 0;
- }
- int A[N-2], B[N-2]; F0R(i, N-2) cin >> A[i];
- F0R(i, N-2) cin >> B[i];
- set<int> foundDifs;
- F0R(i, N-2) {
- foundDifs.insert(B[i] - A[i]);
- }
- if ((sz(foundDifs) == 1 && *foundDifs.begin() != 0) || (sz(foundDifs) == 2 && *foundDifs.begin() == -1 * *foundDifs.rbegin())) {
- cout << "TAK" << endl;
- int val = *foundDifs.begin();
- val = abs(val);
- cout << 1 << " " << N << " " << val << endl;
- F0R(i, N-2) {
- if (A[i] < B[i]) {
- cout << 1 << " " << i+2 << " " << A[i] << endl;
- } else {
- cout << N << " " << i+2 << " " << B[i] << endl;
- }
- }
- return 0;
- }
- int loVal = 2000001;
- map<int, int> minima;
- set<int> minPos;
- bool bad = false;
- F0R(i, N-2) {
- if (A[i] + B[i] < loVal) {
- bad = false;
- minima.clear();
- minPos.clear();
- minPos.insert(i);
- loVal = A[i] + B[i];
- minima.insert(mp(A[i], i));
- } else if (A[i] + B[i] == loVal) {
- if (minima.count(A[i])) bad = true;
- minima.insert({A[i], i});
- minPos.insert(i);
- }
- }
- if (bad) {
- cout << "NIE" << endl;
- return 0;
- }
- vector<vpi> graph(N);
- graph[N-1].pb(mp(minima.rbegin()->s, loVal - minima.rbegin()->f));
- graph[N-2].pb(mp(minima.begin()->s, minima.begin()->f));
- for (auto it = minima.begin(); it != minima.end(); it++) {
- auto it2 = minima.upper_bound(it->f);
- if (it2 == minima.end()) break;
- int A = it->f, B = it->s, C = it2->f, D = it2->s;
- graph[B].pb(mp(D, C-A));
- }
- F0R(i, N-2) {
- if (minPos.count(i)) continue;
- int dif = A[i] - B[i];
- dif += loVal;
- if (dif % 2 == 1) {
- cout << "NIE" << endl; return 0;
- }
- dif /= 2;
- if (dif == 0) {
- graph[N-2].pb(mp(i, A[i]));
- } else if (dif == loVal) {
- graph[N-1].pb(mp(i, B[i]));
- } else if (minima.count(dif)) {
- int pos = minima[dif];
- graph[pos].pb(mp(i, A[i] - dif));
- } else {
- cout << "NIE" << endl; return 0;
- }
- }
- cout << "TAK" << endl;
- F0R(i, N) {
- F0R(j, sz(graph[i])) {
- cout << decomp(i, N) << " " << decomp(graph[i][j].f, N) << " " << graph[i][j].s << endl;
- }
- }
- return 0;
- }
- // read the question correctly (ll vs int)
- // template by bqi343
- // license: https://github.com/bqi343/USACO/blob/master/LICENSE
Advertisement
Add Comment
Please, Sign In to add comment