oj.uz

Submission #227310

# Submission time Handle Problem Language Result Execution time Memory
227310 2020-04-26T18:04:17 Z rqi Mechanical Doll (IOI18_doll) C++14
100 / 100
 209 ms 29472 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef double db; 
typedef string str; 

typedef pair<int,int> pi;
typedef pair<ll,ll> pl; 
typedef pair<db,db> pd; 

typedef vector<int> vi; 
typedef vector<ll> vl; 
typedef vector<db> vd; 
typedef vector<str> vs; 
typedef vector<pi> vpi;
typedef vector<pl> vpl; 
typedef vector<pd> vpd; 

#define mp make_pair 
#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend() 
#define rsz resize
#define ins insert 
#define ft front() 
#define bk back()
#define pf push_front 
#define pb push_back
#define eb emplace_back 
#define lb lower_bound 
#define ub upper_bound 

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; 
const ll INF = 1e18; 
const ld PI = acos((ld)-1);
const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1}; 

template<class T> bool ckmin(T& a, const T& b) { 
  return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { 
  return a < b ? a = b, 1 : 0; } 
int pct(int x) { return __builtin_popcount(x); } 
int bit(int x) { return 31-__builtin_clz(x); } // floor(log2(x)) 
int cdiv(int a, int b) { return a/b+!(a<0||a%b == 0); } // division of a by b rounded up, assumes b > 0 

// INPUT
template<class A> void re(complex<A>& c);
template<class A, class B> void re(pair<A,B>& p);
template<class A> void re(vector<A>& v);
template<class A, size_t SZ> void re(array<A,SZ>& a);

template<class T> void re(T& x) { cin >> x; }
void re(db& d) { str t; re(t); d = stod(t); }
void re(ld& d) { str t; re(t); d = stold(t); }
template<class H, class... T> void re(H& h, T&... t) { re(h); re(t...); }

template<class A> void re(complex<A>& c) { A a,b; re(a,b); c = {a,b}; }
template<class A, class B> void re(pair<A,B>& p) { re(p.f,p.s); }
template<class A> void re(vector<A>& x) { trav(a,x) re(a); }
template<class A, size_t SZ> void re(array<A,SZ>& x) { trav(a,x) re(a); }

// TO_STRING
#define ts to_string
template<class A, class B> str ts(pair<A,B> p);
template<class A> str ts(complex<A> c) { return ts(mp(c.real(),c.imag())); }
str ts(bool b) { return b ? "true" : "false"; }
str ts(char c) { str s = ""; s += c; return s; }
str ts(str s) { return s; }
str ts(const char* s) { return (str)s; }
str ts(vector<bool> v) { 
  bool fst = 1; str res = "{";
  F0R(i,sz(v)) {
    if (!fst) res += ", ";
    fst = 0; res += ts(v[i]);
  }
  res += "}"; return res;
}
template<size_t SZ> str ts(bitset<SZ> b) {
  str res = ""; F0R(i,SZ) res += char('0'+b[i]);
  return res; }
template<class T> str ts(T v) {
  bool fst = 1; str res = "{";
  for (const auto& x: v) {
    if (!fst) res += ", ";
    fst = 0; res += ts(x);
  }
  res += "}"; return res;
}
template<class A, class B> str ts(pair<A,B> p) {
  return "("+ts(p.f)+", "+ts(p.s)+")"; }

// OUTPUT
template<class A> void pr(A x) { cout << ts(x); }
template<class H, class... T> void pr(const H& h, const T&... t) { 
  pr(h); pr(t...); }
void ps() { pr("\n"); } // print w/ spaces
template<class H, class... T> void ps(const H& h, const T&... t) { 
  pr(h); if (sizeof...(t)) pr(" "); ps(t...); }

// DEBUG
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
  cerr << to_string(h); if (sizeof...(t)) cerr << ", ";
  DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 42
#endif

// FILE I/O
void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void unsyncIO() { ios_base::sync_with_stdio(0); cin.tie(0); }
void setIO(string s = "") {
  unsyncIO();
  // cin.exceptions(cin.failbit); 
  // throws exception when do smth illegal
  // ex. try to read letter into int
  if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
}

mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 

int S;
vi A;
vi X;
vi Y;
int N;
int maxlevel;
int trignum = 0;
int curnode = 1;
pair<int, string> triggers[200005];
void assignSwitches(int lvl, string path = ""){
  int node = curnode;
  if(lvl == maxlevel){
    triggers[trignum] = mp(curnode, path+'0');
    trignum++;
    if(trignum == N) return;
    triggers[trignum] = mp(curnode, path+'1');
    trignum++;
    return;
  }
  curnode++;
  Y[node-1] = -(curnode);
  
  assignSwitches(lvl+1, path+'0');
  if(trignum == N) return;
  curnode++;
  X[node-1] = -(curnode);
  
  assignSwitches(lvl+1, path+'1');
}

void create_circuit(int M, vector<int> _A) {

  A = _A;
  A.pb(0);
  reverse(all(A));
  N = sz(A);
  maxlevel = 1+log2(N-1);
  X = vector<int>(2*N+5, -1);
  Y = vector<int>(2*N+5, -1);
  assignSwitches(1);
  /*for(int i = 1; i <= 7; i++){
    ps(i, X[i], Y[i]);
  }
  for(int i = 0; i < N; i++){
    ps(i, triggers[i]);
  }*/
  vector<pi> sorttrigs;
  for(int i = 0; i < N; i++){
    string s = triggers[i].s;
    int num = 0;
    for(int i = 0; i < sz(s); i++){
      num+=(s[i]-'0')*(1<<i);
    }
    sorttrigs.pb(mp(num, i));
  }

  sort(all(sorttrigs));

  for(int i = 0; i < N; i++){
    int ind = sorttrigs[i].s;
    int node = triggers[ind].f;
    //ps(i, ind, node);
    if(triggers[ind].s.bk == '0'){
      Y[node-1] = A[i];
    }
    else{
      X[node-1] = A[i];
    }
  }

  vector<int> C(M+1, 0);
  for (int i = 0; i <= M; ++i) {
    C[i] = -1;
  }

  X.rsz(curnode);
  Y.rsz(curnode);
  //ps(C, X, Y);
  answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void setIn(std::string)':
doll.cpp:124:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 | void setIn(string s) { freopen(s.c_str(),"r",stdin); }
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
doll.cpp: In function 'void setOut(std::string)':
doll.cpp:125:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 | void setOut(string s) { freopen(s.c_str(),"w",stdout); }
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8012 KB Output is correct
2 Correct 68 ms 16064 KB Output is correct
3 Correct 66 ms 15544 KB Output is correct
4 Correct 6 ms 8012 KB Output is correct
5 Correct 19 ms 9292 KB Output is correct
6 Correct 99 ms 19492 KB Output is correct
7 Correct 8 ms 8100 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8012 KB Output is correct
2 Correct 68 ms 16064 KB Output is correct
3 Correct 66 ms 15544 KB Output is correct
4 Correct 6 ms 8012 KB Output is correct
5 Correct 19 ms 9292 KB Output is correct
6 Correct 99 ms 19492 KB Output is correct
7 Correct 8 ms 8100 KB Output is correct
8 Correct 130 ms 21996 KB Output is correct
9 Correct 125 ms 22588 KB Output is correct
10 Correct 194 ms 29472 KB Output is correct
11 Correct 6 ms 8012 KB Output is correct
12 Correct 6 ms 8012 KB Output is correct
13 Correct 8 ms 8012 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8012 KB Output is correct
2 Correct 68 ms 16064 KB Output is correct
3 Correct 66 ms 15544 KB Output is correct
4 Correct 6 ms 8012 KB Output is correct
5 Correct 19 ms 9292 KB Output is correct
6 Correct 99 ms 19492 KB Output is correct
7 Correct 8 ms 8100 KB Output is correct
8 Correct 130 ms 21996 KB Output is correct
9 Correct 125 ms 22588 KB Output is correct
10 Correct 194 ms 29472 KB Output is correct
11 Correct 6 ms 8012 KB Output is correct
12 Correct 6 ms 8012 KB Output is correct
13 Correct 8 ms 8012 KB Output is correct
14 Correct 198 ms 29000 KB Output is correct
15 Correct 119 ms 21588 KB Output is correct
16 Correct 209 ms 28712 KB Output is correct
17 Correct 8 ms 8012 KB Output is correct
18 Correct 5 ms 8012 KB Output is correct
19 Correct 8 ms 8012 KB Output is correct
20 Correct 196 ms 29260 KB Output is correct
21 Correct 7 ms 8012 KB Output is correct
22 Correct 6 ms 8012 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8012 KB Output is correct
2 Correct 7 ms 8012 KB Output is correct
3 Correct 6 ms 8128 KB Output is correct
4 Correct 5 ms 8012 KB Output is correct
5 Correct 5 ms 8012 KB Output is correct
6 Correct 7 ms 8012 KB Output is correct
7 Correct 6 ms 8012 KB Output is correct
8 Correct 6 ms 8076 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8112 KB Output is correct
2 Correct 110 ms 20928 KB Output is correct
3 Correct 110 ms 20968 KB Output is correct
4 Correct 162 ms 27644 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8112 KB Output is correct
2 Correct 110 ms 20928 KB Output is correct
3 Correct 110 ms 20968 KB Output is correct
4 Correct 162 ms 27644 KB Output is correct
5 Correct 185 ms 28540 KB Output is correct
6 Correct 189 ms 28256 KB Output is correct
7 Correct 179 ms 28372 KB Output is correct
8 Correct 175 ms 28028 KB Output is correct
9 Correct 114 ms 21056 KB Output is correct
10 Correct 205 ms 27888 KB Output is correct
11 Correct 200 ms 27576 KB Output is correct
12 Correct 117 ms 20928 KB Output is correct
13 Correct 122 ms 21176 KB Output is correct
14 Correct 110 ms 21356 KB Output is correct
15 Correct 111 ms 21424 KB Output is correct
16 Correct 9 ms 8396 KB Output is correct
17 Correct 106 ms 20880 KB Output is correct
18 Correct 117 ms 20920 KB Output is correct
19 Correct 121 ms 20892 KB Output is correct
20 Correct 197 ms 27776 KB Output is correct
21 Correct 181 ms 27584 KB Output is correct
22 Correct 180 ms 27696 KB Output is correct