Submission #255509

#TimeUsernameProblemLanguageResultExecution timeMemory
255509davitmargMechanical Doll (IOI18_doll)C++17
83.75 / 100
146 ms22264 KiB
/* DavitMarg In a honky-tonk, Down in Mexico */ #include <iostream> #include <algorithm> #include <cmath> #include <vector> #include <string> #include <cstring> #include <map> #include <unordered_map> #include <set> #include <unordered_set> #include <queue> #include <iomanip> #include <bitset> #include <stack> #include <cassert> #include <iterator> #include <fstream> #define mod 1000000007ll #define LL long long #define LD long double #define MP make_pair #define PB push_back #define all(v) v.begin(), v.end() #define fastIO ios::sync_with_stdio(false); cin.tie(0) using namespace std; const int N = 200005; #ifndef death #include "doll.h" #endif // ! death #ifdef death void answer(vector<int> c, vector<int> x, vector<int> y) { cout << "!!" << x.size() << "!!" << endl; for (int i = 0; i < c.size(); i++) cout << c[i] << " "; cout << endl; for (int i = 0; i < x.size(); i++) cout << x[i] << " : " << y[i] << endl; } #endif int bitcount(int x) { int res = 0; while (x) { res += x % 2; x /= 2; } return res; } int n, k,ind[N+N+N]; vector<int> pos[N+N], p, X, Y,nxt; int add() { k++; X.push_back(0); Y.push_back(0); return k; } int han = 0; int inv(int x, int d) { int res = 0; for (int i = 0; i < d; i++) if ((1 << i) & x) res += (1 << (d - 1 - i)); return res; } void build(int st,int d,int val, int c, int x) { int v = k; if (c) { int x2 = x + (1 << (d + c)) - (1 << d); if (inv(x2, c + d + 1) < han) X[v - 1] = -st; else { X[v - 1] = -add(); build(st, d + 1, val, c - 1, x); } x += (1 << d); Y[v - 1] = -add(); build(st, d + 1, val, c - 1, x); } else { int x1 = x; int x2 = x + (1 << d); if (inv(x1, c + d + 1) >= han) X[v - 1] = pos[val][pos[val].size() - 1 - ind[x1]]; else X[v - 1] = -st; if (inv(x2, c + d + 1) >= han) Y[v - 1] = pos[val][pos[val].size() - 1 - ind[x2]]; else Y[v - 1] = -st; } } void solve(int val) { if (pos[val].empty()) return; if (pos[val].size() == 1) { nxt[val] = pos[val][0]; return; } for (int i = 0; i < 30; i++) if ((1 << i) >= pos[val].size()) { nxt[val] = -add(); han = (1 << i) - pos[val].size(); vector<int> id; for (int j = han; j < (1 << i); j++) id.push_back(inv(j, i)); sort(all(id)); for (int j = 0; j < id.size(); j++) ind[id[j]] = j; build(k, 0, val, i-1, 0); break; } } void create_circuit(int M, vector<int> A) { n = M; p = A; p.PB(0); nxt.resize(n + 1); for (int i = p.size() - 2; i >= 0; i--) pos[p[i]].push_back(p[i+1]); for (int i = 1; i <= n; i++) solve(i); nxt[0] = p[0]; answer(nxt, X, Y); } #ifdef death int main() { fastIO; int nn; vector<int> aa; cin >> nn >> nn; for (int i = 1; i <= nn; i++) { int x; cin >> x; aa.push_back(x); } create_circuit(nn, aa); return 0; } #endif /* 1 12 1 2 1 2 1 2 1 2 1 2 1 2 */

Compilation message (stderr)

doll.cpp: In function 'void solve(int)':
doll.cpp:129:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |         if ((1 << i) >= pos[val].size())
      |             ~~~~~~~~~^~~~~~~~~~~~~~~~~~
doll.cpp:137:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |             for (int j = 0; j < id.size(); j++)
      |                             ~~^~~~~~~~~~~
#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...