oj.uz

Submission #587425

# Submission time Handle Problem Language Result Execution time Memory
587425 2022-07-01T21:01:22 Z MilosMilutinovic The Potion of Great Power (CEOI20_potion) C++14
38 / 100
 885 ms 262144 KB 
/**
 *    author:  wxhtzdy
 *    created: 01.07.2022 22:14:54
**/
#include <bits/stdc++.h>

using namespace std;

string to_string(string s) {
  return '"' + s + '"';
}
string to_string(const char* s) {
  return to_string((string) s);
}
string to_string(bool b) {
  return (b ? "true" : "false");
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

const int MAX = 200005;
const int MAGIC = 300;
               
int a[MAX], p[MAX], q[MAX];         
vector<int> qs[MAX];
vector<set<int>> my[MAX];

void init(int n, int d, int h[]) {
  for (int i = 0; i < n; i++) {
    a[i] = h[i];
  }
}

void curseChanges(int u, int a[], int b[]) {
  for (int i = 0; i < u; i++) {
    qs[a[i]].push_back(i);
    qs[b[i]].push_back(i);
    p[i] = a[i];
    q[i] = b[i];
  }                   
  for (int i = 0; i < MAX; i++) {
    if ((int) qs[i].size() <= MAGIC) {
      continue;
    }
    set<int> st;                      
    for (int j : qs[i]) {
      int he = (i ^ p[j] ^ q[j]);
      if (st.find(he) != st.end()) {
        st.erase(st.find(he));
      } else {
        st.insert(he);
      }
      my[i].push_back(st);
    }
  }
}

int question(int x, int y, int v) {
  --v;
  vector<int> xs;
  vector<int> ys;
  if ((int) qs[x].size() <= MAGIC) {
    set<int> st;
    for (int i = 0; i < (int) qs[x].size(); i++) {
      if (qs[x][i] > v) {
        break; 
      }
      int he = (x ^ p[qs[x][i]] ^ q[qs[x][i]]);
      if (st.find(he) != st.end()) {
        st.erase(st.find(he));
      } else {
        st.insert(he);
      }
    }
    debug(st);
    for (int i : st) {
      xs.push_back(a[i]);
    }
    sort(xs.begin(), xs.end());
  } else {
    int i = lower_bound(qs[x].begin(), qs[x].end(), v + 1) - qs[x].begin();
    --i;      
    if (i >= 0 && i < (int) my[x].size()) {   
      for (int vv : my[x][i]) {
        xs.push_back(a[vv]);        
      }
    }
    sort(xs.begin(), xs.end());
  }
  if ((int) qs[y].size() <= MAGIC) {
    set<int> st;
    for (int i = 0; i < (int) qs[y].size(); i++) {
      if (qs[y][i] > v) {
        break; 
      }
      int he = (y ^ p[qs[y][i]] ^ q[qs[y][i]]);
      if (st.find(he) != st.end()) {
        st.erase(st.find(he));
      } else {
        st.insert(he);
      }
    }
    for (int i : st) {
      ys.push_back(a[i]);
    }
    sort(ys.begin(), ys.end());
  } else {
    int i = lower_bound(qs[y].begin(), qs[y].end(), v + 1) - qs[y].begin();
    --i;      
    if (i >= 0 && i < (int) my[y].size()) {   
      for (int vv : my[y][i]) {
        ys.push_back(a[vv]);        
      }
    }
    sort(ys.begin(), ys.end());
  }                 
  debug(xs);
  debug(ys);
  int ptr = 0;
  int ans = 1e9;
  for (int i = 0; i < (int) xs.size(); i++) {
    while (ptr + 1 < (int) ys.size() && xs[i] > ys[ptr]) {
      ptr += 1;
    }   
    for (int j = -1; j <= 1; j++) {
      int idx = ptr + j;
      if (idx >= 0 && idx < (int) ys.size()) {
        ans = min(ans, abs(xs[i] - ys[idx]));
      }
    }
  }
  return ans;  
}

Compilation message

potion.cpp: In function 'int question(int, int, int)':
potion.cpp:45:20: warning: statement has no effect [-Wunused-value]
   45 | #define debug(...) 42
      |                    ^~
potion.cpp:102:5: note: in expansion of macro 'debug'
  102 |     debug(st);
      |     ^~~~~
potion.cpp:45:20: warning: statement has no effect [-Wunused-value]
   45 | #define debug(...) 42
      |                    ^~
potion.cpp:144:3: note: in expansion of macro 'debug'
  144 |   debug(xs);
      |   ^~~~~
potion.cpp:45:20: warning: statement has no effect [-Wunused-value]
   45 | #define debug(...) 42
      |                    ^~
potion.cpp:145:3: note: in expansion of macro 'debug'
  145 |   debug(ys);
      |   ^~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9680 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9680 KB Output is correct
2 Correct 6 ms 9680 KB Output is correct
3 Correct 7 ms 9680 KB Output is correct
4 Correct 16 ms 10564 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 17760 KB Output is correct
2 Correct 166 ms 17780 KB Output is correct
3 Correct 447 ms 212904 KB Output is correct
4 Runtime error 279 ms 262144 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 17800 KB Output is correct
2 Runtime error 310 ms 262144 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 10232 KB Output is correct
2 Correct 283 ms 10076 KB Output is correct
3 Correct 307 ms 17688 KB Output is correct
4 Correct 885 ms 73656 KB Output is correct
5 Correct 877 ms 56380 KB Output is correct
6 Correct 227 ms 9936 KB Output is correct
7 Correct 719 ms 63860 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9680 KB Output is correct
2 Correct 8 ms 9680 KB Output is correct
3 Correct 6 ms 9680 KB Output is correct
4 Correct 7 ms 9680 KB Output is correct
5 Correct 16 ms 10564 KB Output is correct
6 Correct 174 ms 17760 KB Output is correct
7 Correct 166 ms 17780 KB Output is correct
8 Correct 447 ms 212904 KB Output is correct
9 Runtime error 279 ms 262144 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -