Submission #290087

#TimeUsernameProblemLanguageResultExecution timeMemory
290087dandrozavrMechanical Doll (IOI18_doll)C++14
2 / 100
152 ms14932 KiB
#include "doll.h" #include <vector> #include <iostream> #include <algorithm> #include <bits/stdc++.h> #define TIME 1.0 * clock() / CLOCKS_PER_SEC #define pb push_back #define F first #define S second #define _ <<" "<< #define pii pair < int , int > using namespace std; struct seg_tree{ vector < int > t, num; vector < bool > l, r; int n, len, how = 1, bad = 0; seg_tree(){n = len = 0;}; seg_tree(int _n){ n = _n; len = 1; while(len <= n) len <<= 1; t.resize(len << 1 | 1); l.resize(len << 1 | 1); r.resize(len << 1 | 1); num.resize(len << 1 | 1); for (int i = 0; i < num.size(); ++i) num[i] = i; }; void way(int v, int tl, int tr){ if (!t[v]){ t[v] = 2; } else if (t[v] == 1) t[v] = 2; else t[v] = 1; if (tl == tr){ t[v] = how++; return; } int tm = (tl + tr) >> 1; if (t[v] == 1){ way(v << 1, tl, tm); l[v] = 1; }else{ way(v << 1 | 1, tm + 1, tr); r[v] = 1; } } }; vector < int > g[(int)(1e5 + 5)]; void create_circuit (int m, vector < int > a) { int n = a.size(); a.pb(0); vector < int > c; for (int i = 1; i <= n; ++i){ // cout << a[i - 1] << endl; g[a[i - 1]].pb(a[i]); } g[0].pb(a[0]); int now = 1; vector < pii > swit; cerr << TIME << endl; for (int i = 0; i <= m; ++i){ int sz = g[i].size(); if (!sz){ c.pb(0); continue; } if (sz == 1){ c.pb(g[i][0]); } else { vector < int > all; for (int j = 0; j < sz; ++j) all.pb(g[i][j]); seg_tree t; t = seg_tree(sz); int cnt = 0; for (int i = 0; i < sz; ++i){ t.way(1, 0, t.len - 1); } vector < int > vis; vector < int > q; reverse(all.begin(), all.end()); int good[t.t.size() + 1]; int val[t.t.size() + 1]; fill(good, good + t.t.size(), 1); for (int i = t.t.size() - 1; i >= 1; --i) if (t.t[i]){ if (!t.r[i]){ t.num[i] = -all[t.t[i] - 1]; val[i] = t.num[i]; continue; } if (t.l[i] && val[i << 1] != val[i << 1 | 1]) good[i] = 0; else val[i] = val[i << 1 | 1]; if (!t.l[i]) t.num[i << 1] = 1; if (!good[i << 1] || !good[i << 1 | 1]) good[i] = 0; val[i] = val[i << 1 | 1]; // cout << i _ good[i] << endl; } for (int i = 1; i < t.t.size(); ++i) if (t.t[i]){ if (!t.r[i]){ t.num[i] = -all[t.t[i] - 1]; continue; } if (good[i]){ if (good[i] == 3){ if ((i << 1) < t.t.size()) good[i << 1] = good[i << 1 | 1] = 3; continue; } good[i << 1] = good[i << 1 | 1] = 3; t.num[i << 1] = 1; t.num[i << 1 | 1] = val[i]; } vis.pb(i); q.pb(i); if (t.num[i << 1] > 0) q.pb(t.num[i << 1]); if (t.num[i << 1 | 1] > 0) q.pb(t.num[i << 1 | 1]); } reverse(vis.begin(), vis.end()); sort(q.begin(), q.end()); q.resize(unique(q.begin(), q.end()) - q.begin()); unordered_map < int , int > mp; reverse(vis.begin(), vis.end()); for (int i : q) mp[i] = now++; for (int i : vis){ int f = t.num[i << 1]; if (mp.count(f)) f = mp[f]; int s = t.num[i << 1 | 1]; if (mp.count(s)) s = mp[s]; swit.pb({-f, -s}); // cout << i _ -f _ -s _ good[i] << endl; } // cout << vis.size() _ now << endl; // for (int i = 1; i < t.num.size(); ++i) // cout << t.num[i] _ t.t[i] _ t.l[i] _ t.r[i] << endl; // for (auto i : swit) // cout << i.F _ i.S << endl; c.pb(-mp[t.num[1]]); } } cerr << TIME << endl; // for (int i : c) cout << i << " "; // cout << endl; vector < int > X, Y; for (int i = 0; i < swit.size(); ++i){ X.pb(swit[i].F), Y.pb(swit[i].S); // cout << X.back() _ Y.back() << endl; } answer(c, X, Y); }

Compilation message (stderr)

doll.cpp: In constructor 'seg_tree::seg_tree(int)':
doll.cpp:30:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         for (int i = 0; i < num.size(); ++i)
      |                         ~~^~~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:105:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |             for (int i = 1; i < t.t.size(); ++i)
      |                             ~~^~~~~~~~~~~~
doll.cpp:113:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |                             if ((i << 1) < t.t.size())
      |                                 ~~~~~~~~~^~~~~~~~~~~~
doll.cpp:81:17: warning: unused variable 'cnt' [-Wunused-variable]
   81 |             int cnt = 0;
      |                 ^~~
doll.cpp:152:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |     for (int i = 0; i < swit.size(); ++i){
      |                     ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...