Submission #249522

#TimeUsernameProblemLanguageResultExecution timeMemory
249522VimmerPoklon (COCI17_poklon7)C++14
90 / 120
1096 ms118504 KiB
#include <bits/stdc++.h> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> //#pragma GCC optimize("unroll-loops") //#pragma GCC optimize("-O3") //#pragma GCC optimize("Ofast") //#pragma GCC optimize("fast-math") //#pragma GCC optimize("no-stack-protector") #define F first #define S second #define sz(x) int(x.size()) #define pb push_back #define pf push_front #define N 1000010 #define M ll(1e9 + 7) #define inf 1e9 + 1e9 using namespace std; //using namespace __gnu_pbds; typedef long double ld; typedef long long ll;; typedef short int si; typedef array <int, 6> a6; //typedef tree <int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; pair <int, int> val[N]; void tranc(vector <char> &gr, int x) { while (x > 0) { if (x % 2) gr.pb('1'); else gr.pb('0'); x /= 2; } reverse(gr.begin(), gr.end()); } void dfs(vector <char> &gr, int v) { vector <char> l, r; l.clear(); r.clear(); if (val[v].F < 0) dfs(l, abs(val[v].F)); else tranc(l, val[v].F); if (val[v].S < 0) dfs(r, abs(val[v].S)); else tranc(r, val[v].S); if (sz(l) < sz(r)) swap(l, r); if (sz(l) != sz(r)) {gr = l; gr.pb('0'); return;} for (int i = 0; i < sz(l); i++) { if (l[i] == r[i]) continue; if (r[i] == '1') swap(l, r); break; } gr = l; gr.pb('0'); } int main() { //freopen("input.txt", "r", stdin); freopen("output4.txt", "w", stdout); ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; for (int i = 1; i <= n; i++) { int l, r; cin >> l >> r; if (l < 0) val[i].F = abs(l); else val[i].F = -l; if (r < 0) val[i].S = abs(r); else val[i].S = -r; } vector <char> gr; gr.clear(); dfs(gr, 1); for (auto it : gr) cout << it; }
#Verdict Execution timeMemoryGrader output
Fetching results...