Viscious Keyboard
Tutorial is loading...
example code 1
print (lambda s: max((s[:i] + x + s[i+1:]).count("VK") for x in "VK" for i in range(len(s))))(raw_input())
example code 2
print (lambda s: s.count("VK") + int(any(x*3 in "K" + s + "V" for x in "VK")))(raw_input())
Valued Keys
Tutorial is loading...
example code
x,y = raw_input(), raw_input()
print all(a>=b for a,b in zip(x,y)) * y or "-1"
Voltage Keepsake
Tutorial is loading...
example code (c++)
#include <stdio.h>
#include <algorithm>
#include <assert.h>
using namespace std;
typedef long long ll;
typedef long double ld;
// Adjust MAXN for bounds
const ll MAXN=1e5+4;
// MAXV is the max amount of time we can take
const ld MAXV=1e18;
ll a[MAXN],b[MAXN];
ld exhaust[MAXN];
int n;
ll P;
bool f(ld imid) {
ld needsum=0;
for (int i=0;i<n;i++) {
ld need=max(0.0L, (imid-exhaust[i])*a[i]);
needsum+=need;
}
ld supply=imid*P;
return supply>=needsum;
}
int main()
{
scanf("%d%lld",&n,&P);
for (int i=0;i<n;i++) {
scanf("%lld%lld",&a[i],&b[i]);
}
ll suma=0;
for (int i=0;i<n;i++) {
suma+=a[i];
}
if (P>=suma) {
printf("-1\n");
return 0;
}
for (int i=0;i<n;i++) {
exhaust[i]=((ld)b[i])/((ld)a[i]);
}
ld imin=0,imax=MAXV;
for (ll iter=0;iter<220;iter++) {
ld imid=(imin+imax)/2;
if (f(imid)) imin=imid;
else imax=imid;
}
if (imax>MAXV-100) printf("-1\n");
else printf("%.9f\n",(double)imin);
}
Volatile Kite
Tutorial is loading...
example code (c++)
#include <bits/stdc++.h>
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge {c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
*this << "[";
for (auto it = d.b; it != d.e; ++it)
*this << ", " + 2 * (it == d.b) << *it;
ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
typedef long double ld;
typedef long double ll;
ld K(ld a) { return a * a; }
struct P {
ll x, y;
void read() { cin >> x >> y; }
P operator + (P b) { return P{x + b.x, y + b.y}; }
P operator - (P b) { return P{x - b.x, y - b.y}; }
P operator * (ld/*ll*/ mul) { return P{x * mul, y * mul}; }
ll operator * (P b) { return x * b.y - y * b.x; }
ll dot(P b) { return x * b.x + y * b.y; }
ld len() { return sqrt(K(x) + K(y)); }
P lenTo(ld to) { return *this * (to / len()); }
ld dist(P & b) { return (*this - b).len(); }
};
struct L2 {
P one, two;
ld dist(P he) {
return abs((he - one) * (he - two)) / one.dist(two);
}
};
int main() {
int n;
cin >> n;
vector<P> points(n);
for(P & p : points)
p.read();
ld answer = 1e15;
for(int i = 0; i < n; ++i)
for(int j = 0; j < 2 * n; ++j)
if(abs(i - j) <= 2)
for(int k = 0; k < 2 * n; ++k)
if(abs(i - k) <= 2 && (int) set<int>{i % n, j % n, k % n}.size() == 3)
answer = min(answer, L2{points[i%n], points[j%n]}.dist(points[k%n]));
printf("%.10lf\n", (double) answer / 2);
}
example code (java)
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;
/**
* Built using CHelper plug-in
* Actual solution is at the top
*/
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
OutputWriter out = new OutputWriter(outputStream);
NonConvexPolygon solver = new NonConvexPolygon();
solver.solve(1, in, out);
out.close();
}
static class NonConvexPolygon {
public void solve(int testNumber, InputReader in, OutputWriter out) {
int n = in.nextInt();
long[][] p = new long[n][2];
for (int i = 0; i < n; i++) {
p[i][0] = in.nextInt();
p[i][1] = in.nextInt();
}
double ans = 1L << 60;
for (int i = 0; i < n; i++) {
int prev = (i + n - 1) % n, next = (i + 1) % n;
ans = Math.min(ans, PointToSegmentDistance.pointToLineThroughTwoPointsDistance(
p[i][0], p[i][1], p[prev][0], p[prev][1], p[next][0], p[next][1]
) / 2.0);
}
out.printf("%.10f\n", ans);
}
}
static class Utils {
public static double cross(Point a, Point b, Point c) {
Point ab = new Point(b.x - a.x, b.y - a.y);
Point ac = new Point(c.x - a.x, c.y - a.y);
return ab.x * ac.y - ab.y * ac.x;
}
}
static class PointToSegmentDistance {
static double fastHypot(double x, double y) {
return Math.sqrt(x * x + y * y);
}
public static double pointToLineThroughTwoPointsDistance(long x, long y, long ax, long ay, long bx, long by) {
double t = Utils.cross(new Point(ax, ay), new Point(bx, by), new Point(x, y));
return Math.abs(t / fastHypot(ax - bx, ay - by));
}
}
static class Point implements Comparable<Point> {
public double x;
public double y;
public double angle;
public int idx;
public Point(double x, double y) {
this.x = x;
this.y = y;
angle = 0;
}
public Point(double x, double y, int idx) {
this.x = x;
this.y = y;
this.idx = idx;
}
public int compareTo(Point other) {
return x == other.x ? (int) Math.signum(y - other.y) : (int) Math.signum(x - other.x);
}
}
static class OutputWriter {
private final PrintWriter writer;
public OutputWriter(OutputStream outputStream) {
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
}
public OutputWriter(Writer writer) {
this.writer = new PrintWriter(writer);
}
public void printf(String format, Object... objects) {
writer.printf(format, objects);
}
public void close() {
writer.close();
}
}
static class InputReader {
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
public InputReader(InputStream stream) {
this.stream = stream;
}
public int read() {
if (this.numChars == -1) {
throw new InputMismatchException();
} else {
if (this.curChar >= this.numChars) {
this.curChar = 0;
try {
this.numChars = this.stream.read(this.buf);
} catch (IOException var2) {
throw new InputMismatchException();
}
if (this.numChars <= 0) {
return -1;
}
}
return this.buf[this.curChar++];
}
}
public int nextInt() {
int c;
for (c = this.read(); isSpaceChar(c); c = this.read()) {
;
}
byte sgn = 1;
if (c == 45) {
sgn = -1;
c = this.read();
}
int res = 0;
while (c >= 48 && c <= 57) {
res *= 10;
res += c - 48;
c = this.read();
if (isSpaceChar(c)) {
return res * sgn;
}
}
throw new InputMismatchException();
}
public static boolean isSpaceChar(int c) {
return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
}
}
}
Vulnerable Kerbals
Tutorial is loading...
example code (c++)
#include <bits/stdc++.h>
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge {c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
*this << "[";
for (auto it = d.b; it != d.e; ++it)
*this << ", " + 2 * (it == d.b) << *it;
ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
const int nax = 2e5 + 5;
bool forbidden[nax];
int my_gcd(int a, int b) {
if(a == 0 || b == 0) return max(a, b); // return m
return __gcd(a, b);
}
#define __gcd use____my_gcd
vector<int> which[nax];
pair<int,int> dp[nax];
int my_pow(int a, int b, int m) {
int r = 1;
while(b) {
if(b % 2) r = (long long) r * a % m;
a = (long long) a * a % m;
b /= 2;
}
return r;
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
while(n--) {
int x;
scanf("%d", &x);
forbidden[x] = true;
}
#define n use_____m
for(int i = 0; i < m; ++i)
if(!forbidden[i])
which[my_gcd(i, m)].push_back(i);
if(forbidden[0])
which[m].push_back(0); // hack
for(int i = 1; i <= m; ++i)
if(!which[i].empty()) {
dp[i] = {0, 0};
for(int j = 1; j < i; ++j)
if(i % j == 0 && dp[j].first > 0)
dp[i] = max(dp[i], make_pair(dp[j].first, j));
dp[i].first += which[i].size();
}
vector<int> ans;
int x = m;
while(!which[x].empty()) {
for(int y : which[x])
ans.push_back(y);
x = dp[x].second;
}
reverse(ans.begin(), ans.end());
if(forbidden[0]) {
assert(!ans.empty());
ans.pop_back();
}
debug() << imie(ans);
int previous = 1;
printf("%d\n", (int) ans.size());
int cnt_coprime = 0;
for(int i = 2; i < m; ++i)
if(my_gcd(i, m) == 1)
++cnt_coprime;
for(int nxt : ans) {
if(nxt == 0) {
printf("0");
continue;
}
int a = previous / my_gcd(m, previous);
int b = nxt / my_gcd(m, nxt);
int print = (long long) b * my_pow(a, cnt_coprime, m) % m;
print = (long long) print * my_gcd(m, nxt) / my_gcd(m, previous) % m;
printf("%d ", print);
previous = nxt;
}
puts("");
}
example code (java)
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.ArrayList;
import java.io.InputStream;
/**
* Built using CHelper plug-in
* Actual solution is at the top
*/
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
OutputWriter out = new OutputWriter(outputStream);
PrefixProductSequence solver = new PrefixProductSequence();
solver.solve(1, in, out);
out.close();
}
static class PrefixProductSequence {
public int[] div;
public boolean[] forbidden;
public ArrayList<Long> ans;
public int n;
public int m;
public void solve(int testNumber, InputReader in, OutputWriter out) {
n = in.nextInt();
m = in.nextInt();
forbidden = new boolean[m + 1];
for (int i = 0; i < n; i++) {
forbidden[in.nextInt()] = true;
}
int[] add = new int[m + 1];
for (int i = 0; i < m; i++) {
if (!forbidden[i]) {
int g = Utils.gcd(i, m);
add[m / g]++;
}
}
int[] arr = new int[m + 1];
div = new int[m + 1];
Arrays.fill(arr, 1);
Arrays.setAll(div, x -> x);
for (int i = 2; i <= m; i++) {
arr[i] += add[i];
for (int j = i + i; j <= m; j += i) {
if (arr[i] > arr[j]) {
arr[j] = arr[i];
div[j] = j / i;
}
}
}
ans = new ArrayList<>();
solve(1, 1);
out.println(ans.size());
boolean first = true;
for (long x : ans) {
if (!first) out.print(" ");
out.print(x);
first = false;
}
out.println();
}
public void solve(int cmult, long mm) {
if (cmult == m) {
if (!forbidden[0]) {
ans.add(0L);
}
return;
}
int prev = 1;
boolean has = false;
for (int i = 1; i < m / cmult; i++) {
if (!forbidden[i * cmult] && Utils.gcd(m / cmult, i) == 1) {
long x = Utils.inv(prev, m / cmult) * i % m;
if (!has) {
has = true;
x = x * mm % m;
}
ans.add(x);
prev = i;
}
}
long nmm = Utils.inv(prev, m / cmult) * div[m / cmult] % m;
if (!has) nmm = nmm * mm % m;
solve(cmult * div[m / cmult], nmm);
}
}
static class OutputWriter {
private final PrintWriter writer;
public OutputWriter(OutputStream outputStream) {
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
}
public OutputWriter(Writer writer) {
this.writer = new PrintWriter(writer);
}
public void print(Object... objects) {
for (int i = 0; i < objects.length; i++) {
if (i != 0) {
writer.print(' ');
}
writer.print(objects[i]);
}
}
public void println() {
writer.println();
}
public void close() {
writer.close();
}
public void print(long i) {
writer.print(i);
}
public void println(int i) {
writer.println(i);
}
}
static class InputReader {
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
public InputReader(InputStream stream) {
this.stream = stream;
}
public int read() {
if (this.numChars == -1) {
throw new InputMismatchException();
} else {
if (this.curChar >= this.numChars) {
this.curChar = 0;
try {
this.numChars = this.stream.read(this.buf);
} catch (IOException var2) {
throw new InputMismatchException();
}
if (this.numChars <= 0) {
return -1;
}
}
return this.buf[this.curChar++];
}
}
public int nextInt() {
int c;
for (c = this.read(); isSpaceChar(c); c = this.read()) {
;
}
byte sgn = 1;
if (c == 45) {
sgn = -1;
c = this.read();
}
int res = 0;
while (c >= 48 && c <= 57) {
res *= 10;
res += c - 48;
c = this.read();
if (isSpaceChar(c)) {
return res * sgn;
}
}
throw new InputMismatchException();
}
public static boolean isSpaceChar(int c) {
return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
}
}
static class Utils {
public static long inv(long N, long M) {
long x = 0, lastx = 1, y = 1, lasty = 0, q, t, a = N, b = M;
while (b != 0) {
q = a / b;
t = a % b;
a = b;
b = t;
t = x;
x = lastx - q * x;
lastx = t;
t = y;
y = lasty - q * y;
lasty = t;
}
return (lastx + M) % M;
}
public static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}
}
Varying Kibibits
Tutorial is loading...
example code (c++, inclusion/exclusion approach)
// vvvvvvvvvvvvvvvvv Library code start
#include <array>
#define NDEBUG
NDEBUG
#include <algorithm>
#include <cassert>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <memory>
#include <queue>
#include <random>
#define forn(t, i, n) for (t i = 0; i < (n); ++i)
#define rforn(t, i, n) for (t i = (n) - 1; i >= 0; --i)
#define all(c) c.begin(), c.end()
using namespace std;
/// caide keep
bool __hack = std::ios::sync_with_stdio(false);
/// caide keep
auto __hack1 = cin.tie(nullptr);
// Section with adoption of array and vector algorithms.
// 32 bit ints (sum LSB + MSB == 32)
// TODO: Section with some container algorithms
#define ENABLE_IF(e) typename enable_if<e>::type* = nullptr
namespace template_util {
template<class T>
constexpr T min(T a, T b) {
return a < b ? a : b;
}
constexpr int bytecount(uint64_t x) {
return x ? 1 + bytecount(x >> 8) : 0;
}
/// caide keep
template<int N>
struct bytetype {
typedef uint64_t type;
};
/// caide keep
template<>
struct bytetype<4> {
typedef uint32_t type;
};
/// caide keep
template<>
struct bytetype<3> {
};
/// caide keep
template<>
struct bytetype<2> {
};
/// caide keep
template<>
struct bytetype<1> {
typedef uint8_t type;
};
/// caide keep
template<>
struct bytetype<0> {
typedef uint8_t type;
};
/// caide keep
template<uint64_t N>
struct minimal_uint : bytetype<bytecount(N)> {
};
}
template<class T>
T next(istream& in) {
T ret;
in >> ret;
return ret;
}
template<class T>
vector<T> next_vector(istream& in, size_t n) {
vector<T> ret(n);
for (size_t i = 0; i < n; ++i) {
ret[i] = next<T>(in);
}
return ret;
}
#define dbg(...) ;
/*
TODOs:
cache invs
primitive root
discrete log
tests!!!
*/
namespace mod_impl {
/// caide keep
template <class T>
constexpr inline T mod(T MOD) {
return MOD;
}
/// caide keep
template <class T>
constexpr inline T mod(T* MOD) {
return *MOD;
}
/// caide keep
template <class T>
constexpr inline T max_mod(T MOD) {
return MOD - 1;
}
/// caide keep
template <class T>
constexpr inline T max_mod(T*) {
return numeric_limits<T>::max() - 1;
}
constexpr inline uint64_t combine_max_sum(uint64_t a, uint64_t b) {
return a > ~b ? 0 : a + b;
}
constexpr inline uint64_t combine_max_mul(uint64_t a, uint64_t b) {
return a > numeric_limits<uint64_t>::max() / b ? 0 : a * b;
}
/// caide keep
template <class T>
constexpr inline uint64_t next_divisible(T mod, uint64_t max) {
return max % mod == 0 ? max : combine_max_sum(max, mod - max % mod);
}
/// caide keep
template <class T>
constexpr inline uint64_t next_divisible(T*, uint64_t) {
return 0;
}
//caide keep
constexpr int IF_THRESHOLD = 2;
template <class T, T MOD_VALUE, uint64_t MAX,
class RET = typename template_util::minimal_uint<max_mod(MOD_VALUE)>::type,
ENABLE_IF(MAX <= max_mod(MOD_VALUE) && !is_pointer<T>::value)>
inline RET smart_mod(typename template_util::minimal_uint<MAX>::type value) {
return value;
}
template <class T, T MOD_VALUE, uint64_t MAX,
class RET = typename template_util::minimal_uint<max_mod(MOD_VALUE)>::type,
ENABLE_IF(max_mod(MOD_VALUE) < MAX && MAX <= IF_THRESHOLD * max_mod(MOD_VALUE) && !is_pointer<T>::value)>
inline RET smart_mod(typename template_util::minimal_uint<MAX>::type value) {
while (value >= mod(MOD_VALUE)) {
value -= mod(MOD_VALUE);
}
return (RET)value;
}
template <class T, T MOD_VALUE, uint64_t MAX,
class RET = typename template_util::minimal_uint<max_mod(MOD_VALUE)>::type,
ENABLE_IF(IF_THRESHOLD * max_mod(MOD_VALUE) < MAX || is_pointer<T>::value)>
inline RET smart_mod(typename template_util::minimal_uint<MAX>::type value) {
return (RET)(value % mod(MOD_VALUE));
}
}
#define MOD mod_impl::mod(MOD_VALUE)
#define MAX_MOD mod_impl::max_mod(MOD_VALUE)
struct DenormTag {};
template <class T, T MOD_VALUE, uint64_t MAX = MAX_MOD, ENABLE_IF(MAX_MOD >= 2)>
struct ModVal {
typedef typename template_util::minimal_uint<MAX>::type storage;
storage value;
/// caide keep
inline ModVal(): value(0) {
assert(MOD >= 2);
}
inline ModVal(storage v, DenormTag): value(v) {
assert(MOD >= 2);
assert(v <= MAX);
};
inline operator ModVal<T, MOD_VALUE>() {
return {v(), DenormTag()};
};
explicit inline operator uint64_t() const {
return v();
}
typename template_util::minimal_uint<mod_impl::max_mod(MOD_VALUE)>::type v() const {
return mod_impl::smart_mod<T, MOD_VALUE, MAX>(value);
}
};
template <class T, T MOD_VALUE, uint64_t MAX,
uint64_t NEW_MAX = mod_impl::next_divisible(MOD_VALUE, MAX),
ENABLE_IF(NEW_MAX != 0),
class Ret = ModVal<T, MOD_VALUE, NEW_MAX>>
inline Ret operator-(const ModVal<T, MOD_VALUE, MAX>& o) {
static_assert(NEW_MAX <= numeric_limits<typename Ret::storage>::max(), "bad unary minus template");
assert(NEW_MAX % MOD == 0 && o.value <= NEW_MAX);
return {typename Ret::storage(NEW_MAX - o.value), DenormTag()};
}
template <class T, T MOD_VALUE, uint64_t MAX1, uint64_t MAX2,
uint64_t NEW_MAX = mod_impl::combine_max_sum(MAX1, MAX2),
ENABLE_IF(NEW_MAX != 0), class Ret = ModVal<T, MOD_VALUE, NEW_MAX>>
inline Ret operator+(ModVal<T, MOD_VALUE, MAX1> o1, ModVal<T, MOD_VALUE, MAX2> o2) {
return {typename Ret::storage(typename Ret::storage() + o1.value + o2.value), DenormTag()};
}
template <class T, T MOD_VALUE, uint64_t MAX1, uint64_t MAX2,
uint64_t NEW_MAX = mod_impl::combine_max_mul(MAX1, MAX2),
ENABLE_IF(NEW_MAX != 0), class Ret = ModVal<T, MOD_VALUE, NEW_MAX>>
inline Ret operator*(ModVal<T, MOD_VALUE, MAX1> o1, ModVal<T, MOD_VALUE, MAX2> o2) {
return {typename Ret::storage(typename Ret::storage(1) * o1.value * o2.value), DenormTag()};
}
template <class T, T MOD_VALUE, uint64_t MAX1, uint64_t MAX2,
uint64_t NEW_MAX = mod_impl::combine_max_mul(MAX1, MAX2),
uint64_t NEW_MAX1 = mod_impl::combine_max_mul(MAX_MOD, template_util::min(MAX1, MAX2)),
ENABLE_IF(NEW_MAX == 0 && NEW_MAX1 != 0 && MAX1 <= MAX2),
class Ret = ModVal<T, MOD_VALUE, mod_impl::combine_max_mul(MAX1, MAX_MOD)>>
inline Ret operator*(const ModVal<T, MOD_VALUE, MAX1>& o1, const ModVal<T, MOD_VALUE, MAX2>& o2) {
return {typename Ret::storage(typename Ret::storage(1) * o1.value * o2.v()), DenormTag()};
}
template <class T, T MOD_VALUE, uint64_t MAX1, uint64_t MAX2,
uint64_t NEW_MAX = mod_impl::combine_max_mul(MAX1, MAX2),
uint64_t NEW_MAX1 = mod_impl::combine_max_mul(MAX_MOD, template_util::min(MAX1, MAX2)),
ENABLE_IF(NEW_MAX == 0 && NEW_MAX1 != 0 && MAX2 < MAX1),
class Ret = ModVal<T, MOD_VALUE, mod_impl::combine_max_mul(MAX_MOD, MAX2)>>
inline Ret operator*(const ModVal<T, MOD_VALUE, MAX1>& o1, const ModVal<T, MOD_VALUE, MAX2>& o2) {
return {typename Ret::storage(typename Ret::storage(1) * o1.v() * o2.value), DenormTag()};
}
template <class T, T MOD_VALUE, uint64_t MAX1, uint64_t MAX2>
inline auto operator-(const ModVal<T, MOD_VALUE, MAX1>& lhs, const ModVal<T, MOD_VALUE, MAX2>& rhs) -> decltype(lhs + (-rhs)) {
return lhs + (-rhs);
}
template <class T, T MOD_VALUE, uint64_t MAX>
inline ModVal<T, MOD_VALUE>& operator+=(ModVal<T, MOD_VALUE>& lhs, const ModVal<T, MOD_VALUE, MAX>& rhs) {
lhs = lhs + rhs;
return lhs;
}
template <class T, T MOD_VALUE, uint64_t MAX>
inline ModVal<T, MOD_VALUE>& operator-=(ModVal<T, MOD_VALUE>& lhs, const ModVal<T, MOD_VALUE, MAX>& rhs) {
lhs = lhs - rhs;
return lhs;
}
template <class T, T MOD_VALUE, uint64_t MAX1, uint64_t MAX2>
inline bool operator!=(const ModVal<T, MOD_VALUE, MAX1>& lhs, const ModVal<T, MOD_VALUE, MAX2>& rhs) {
return lhs.v() != rhs.v();
}
template <class T, T MOD_VALUE, class MOD_TYPE>
struct ModCompanion {
typedef MOD_TYPE mod_type;
typedef ModVal<mod_type, MOD_VALUE> type;
template <uint64_t C>
inline static constexpr ModVal<mod_type, MOD_VALUE, C> c() {
return {C, DenormTag()};
};
template <uint64_t MAX = numeric_limits<uint64_t>::max()>
inline static ModVal<mod_type, MOD_VALUE, MAX> wrap(uint64_t x) {
assert(x <= MAX);
return {typename ModVal<mod_type, MOD_VALUE, MAX>::storage(x), DenormTag()};
};
template <uint64_t MAX, ENABLE_IF(!is_pointer<T>::value && MAX <= MAX_MOD)>
inline static ModVal<mod_type, MOD_VALUE> inv(const ModVal<mod_type, MOD_VALUE, MAX>& x) {
if (x.value == 1) {
return c<1>();
}
return -(wrap<MAX_MOD / 2>(MOD / x.value) * inv(wrap<MAX>(MOD % x.value)));
};
};
#undef MOD
#undef MAX_MOD
template <uint64_t MOD_VALUE>
struct Mod : ModCompanion<uint64_t, MOD_VALUE, typename template_util::minimal_uint<MOD_VALUE>::type> {
template<uint64_t VAL>
static constexpr uint64_t literal_builder() {
return VAL;
}
template<uint64_t VAL, char DIGIT, char... REST>
static constexpr uint64_t literal_builder() {
return literal_builder<(10 * VAL + DIGIT - '0') % MOD_VALUE, REST...>();
}
};
#define REGISTER_MOD_LITERAL(mod, suffix) \
template <char... DIGITS> mod::type operator "" _##suffix() { \
return mod::c<mod::literal_builder<0, DIGITS...>()>(); \
}
// ^^^^^^^^^^^^^^^^^ Library code end
using md = Mod<1000000007>;
using mt = md::type;
REGISTER_MOD_LITERAL(md, mod)
using Val = tuple<int, mt, mt>;
mt pow2s[1000001], powInv2s[1000001];
mt pow2(int p) {
return p < 0 ? powInv2s[-p] : pow2s[p];
}
Val mul(Val a, Val b) {
const mt p2a = pow2(get<0>(a));
const mt p2b = pow2(get<0>(b));
return Val{get<0>(a) + get<0>(b), p2a * get<1>(b) + get<1>(a) * p2b, p2a * get<2>(b) + 2_mod * get<1>(a) * get<1>(b) + get<2>(a) * p2b};
}
Val inv(Val a) {
Val b;
get<0>(b) = -get<0>(a);
const mt p2b = pow2(get<0>(b));
get<1>(b) = -p2b * (get<1>(a) * p2b);
get<2>(b) = -p2b * (2_mod * get<1>(a) * get<1>(b) + get<2>(a) * p2b);
return b;
}
Val d[1000000][7];
mt dSum[1000000][7];
void solve(istream& in, ostream& out) {
pow2s[0] = powInv2s[0] = 1_mod;
mt inv2 = md::inv(2_mod);
forn (int, i, 1000000) {
pow2s[i + 1] = pow2s[i] * 2_mod;
powInv2s[i + 1] = powInv2s[i] * inv2;
}
int n = next<int>(in);
auto as = next_vector<int>(in, n);
sort(all(as));
uint64_t ans = 0;
int add[1 << 6];
forn (int, mask, 1 << 6) {
add[mask] = 0;
int mask1 = mask;
forn (int, it, 6) {
add[mask] = add[mask] * 10 + (mask1 & 1);
mask1 /= 2;
}
}
int asIt = n - 1;
rforn (int, x, 1000000) {
int badMask = 0;
int x1 = x;
forn (int, it, 6) {
badMask = 2 * badMask + (x1 % 10 == 9 ? 1 : 0);
x1 /= 10;
}
d[x][0] = Val{0, 0_mod, 0_mod};
dSum[x][0] = 0_mod;
forn (int, bit, 6) {
d[x][bit + 1] = d[x][bit];
dSum[x][bit + 1] = dSum[x][bit];
if (!(badMask & (1 << bit))) {
d[x][bit + 1] = mul(d[x][bit + 1], inv(d[x + add[1 << bit]][bit]));
dSum[x][bit + 1] -= dSum[x + add[1 << bit]][bit];
}
}
auto val = inv(d[x][6]);
while (asIt >= 0 && as[asIt] == x) {
--asIt;
val = mul(val, Val{1, md::wrap(x), md::wrap(1ULL * x * x)});
}
auto sum = get<2>(val) + dSum[x][6];
forn (int, bit, 6) {
d[x][bit] = mul(d[x][bit], val);
dSum[x][bit] += get<2>(val);
}
if (sum != 0_mod) {
dbg(x, sum, x * uint64_t(sum));
ans ^= x * uint64_t(sum);
}
}
out << ans << endl;
}
int main() {
solve(cin, cout);
return 0;
}
example code (java, FWHT approach)
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;
/**
* Built using CHelper plug-in
* Actual solution is at the top
*/
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
OutputWriter out = new OutputWriter(outputStream);
MinAddition solver = new MinAddition();
solver.solve(1, in, out);
out.close();
}
static class MinAddition {
public int[] pow10 = {1, 10, 100, 1000, 10000, 100000, 1000000};
public int MAXN = 1000000;
public int LOG = 6;
public int mod = 1000000007;
public void solve(int testNumber, InputReader in, OutputWriter out) {
int n = in.nextInt();
int[] freq = new int[MAXN];
int[] sum = new int[MAXN];
int[] sum2 = new int[MAXN];
int[] pow2 = new int[n + 1];
pow2[0] = 1;
for (int i = 1; i <= n; i++) pow2[i] = (pow2[i - 1] << 1) % mod;
for (int i = 0; i < n; i++) {
int a = in.nextInt();
freq[a]++;
sum[a] += a;
if (sum[a] >= mod) sum[a] -= mod;
int x = (int) (1L * a * a % mod);
sum2[a] += x;
if (sum2[a] >= mod) sum2[a] -= mod;
}
int[] mod10 = new int[MAXN];
for (int i = 0; i < 10; i++) mod10[i] = i;
for (int i = 10; i < MAXN; i++) mod10[i] = mod10[i - 10];
for (int level = LOG - 1; level >= 0; level--) {
for (int i = MAXN - 1; i >= 0; i--) {
int d = mod10[i / pow10[level]];
if (d > 0) {
int p = i - pow10[level];
freq[p] += freq[i];
sum[p] += sum[i];
if (sum[p] >= mod) sum[p] -= mod;
sum2[p] += sum2[i];
if (sum2[p] >= mod) sum2[p] -= mod;
}
}
}
for (int i = 0; i < MAXN; i++) {
int sdiff = (int) ((1L * sum[i] * sum[i] + mod - sum2[i]) % mod);
int ssame = sum2[i];
int g = 0;
if (freq[i] >= 1)
g += (int) (1L * ssame * pow2[freq[i] - 1] % mod);
if (freq[i] >= 2)
g += (int) (1L * sdiff * pow2[freq[i] - 2] % mod);
while (g >= mod) g -= mod;
freq[i] = g;
}
for (int level = 0; level < LOG; level++) {
for (int i = 0; i < MAXN; i++) {
int d = mod10[i / pow10[level]];
if (d + 1 < 10) {
int p = i + pow10[level];
freq[i] -= freq[p];
if (freq[i] < 0) freq[i] += mod;
}
}
}
long s = 0;
for (int i = 0; i < MAXN; i++) {
s ^= 1L * i * freq[i];
}
out.println(s);
}
}
static class OutputWriter {
private final PrintWriter writer;
public OutputWriter(OutputStream outputStream) {
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
}
public OutputWriter(Writer writer) {
this.writer = new PrintWriter(writer);
}
public void close() {
writer.close();
}
public void println(long i) {
writer.println(i);
}
}
static class InputReader {
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
public InputReader(InputStream stream) {
this.stream = stream;
}
public int read() {
if (this.numChars == -1) {
throw new InputMismatchException();
} else {
if (this.curChar >= this.numChars) {
this.curChar = 0;
try {
this.numChars = this.stream.read(this.buf);
} catch (IOException var2) {
throw new InputMismatchException();
}
if (this.numChars <= 0) {
return -1;
}
}
return this.buf[this.curChar++];
}
}
public int nextInt() {
int c;
for (c = this.read(); isSpaceChar(c); c = this.read()) {
;
}
byte sgn = 1;
if (c == 45) {
sgn = -1;
c = this.read();
}
int res = 0;
while (c >= 48 && c <= 57) {
res *= 10;
res += c - 48;
c = this.read();
if (isSpaceChar(c)) {
return res * sgn;
}
}
throw new InputMismatchException();
}
public static boolean isSpaceChar(int c) {
return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
}
}
}
Verifying Kingdom
Tutorial is loading...
example code (c++)
// vvvvvvvvvvvvvvvvv Library code start
#define NDEBUG
NDEBUG
#include <algorithm>
#include <array>
#include <cassert>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <memory>
#include <queue>
#include <random>
#define forn(t, i, n) for (t i = 0; i < (n); ++i)
#define foran(t, i, a, n) for (t i = (a); i < (n); ++i)
using namespace std;
/// caide keep
bool __hack = std::ios::sync_with_stdio(false);
/// caide keep
auto __hack1 = cin.tie(nullptr);
template<class T>
inline T mn(T arg) {
return arg;
}
template<class T, class... Args>
inline bool rmx(T &to, Args... args) {
auto v = mn(args...);
if (to < v) {
to = v;
return true;
}
return false;
}
// Section with adoption of array and vector algorithms.
// 32 bit ints (sum LSB + MSB == 32)
// TODO: Section with some container algorithms
namespace template_util {
constexpr int bytecount(uint64_t x) {
return x ? 1 + bytecount(x >> 8) : 0;
}
/// caide keep
template<int N>
struct bytetype {
};
/// caide keep
template<>
struct bytetype<4> {
};
/// caide keep
template<>
struct bytetype<3> {
};
/// caide keep
template<>
struct bytetype<2> {
};
/// caide keep
template<>
struct bytetype<1> {
};
/// caide keep
template<>
struct bytetype<0> {
};
/// caide keep
template<uint64_t N>
struct minimal_uint : bytetype<bytecount(N)> {
};
}
template<class T>
T next(istream& in) {
T ret;
in >> ret;
return ret;
}
// ^^^^^^^^^^^^^^^^^ Library code end
int tr[1000][3];
int l[1000], r[1000];
bool col[1000];
int ans[2000];
tuple<int, int, int> chooseDfs(int total, int i, int p = -1) {
int size = 1, best = -1, bestSize = 1000000000, maxSize = 0;
forn (int, e, 3) {
int j = tr[i][e];
if (j != p && j >= 0 && !col[j]) {
auto r1 = chooseDfs(total, j, i);
if (get<1>(r1) < bestSize) {
best = get<0>(r1);
bestSize = get<1>(r1);
}
size += get<2>(r1);
rmx(maxSize, get<2>(r1));
}
}
rmx(maxSize, total - size);
if (maxSize < bestSize) {
best = i;
bestSize = maxSize;
}
return tuple<int, int, int>{best, bestSize, size};
}
int sizeDfs(int i, int p = -1) {
auto r = 1;
forn (int, e, 3) {
int j = tr[i][e];
if (j != p && j >= 0 && !col[j]) {
r += sizeDfs(j, i);
}
}
return r;
}
void ansDfs(int n, int i) {
forn (int, e, 2) {
if (tr[i][e] >= 0) {
ansDfs(n, tr[i][e]);
}
ans[tr[i][e] < 0 ? -2 - tr[i][e] : n + tr[i][e]] = n + i + 1;
}
}
void solve(istream& in, ostream& out) {
auto q = [&](int a, int b, int c) {
out << a + 1 << " " << b + 1 << " " << c + 1 << endl;
string s = next<string>(in);
if (s == "X") {
return 2;
} else if (s == "Y") {
return 1;
} else if (s == "Z") {
return 0;
} else {
throw 42;
}
};
int n = next<int>(in);
memset(tr, -1, sizeof(tr));
tr[0][0] = -2;
tr[0][1] = -3;
l[0] = 0;
r[0] = 1;
foran (int, i, 2, n) {
memset(col, 0, sizeof(col));
int x = 0;
while (true) {
x = get<0>(chooseDfs(sizeDfs(x), x));
int e = q(l[x], r[x], i);
if (tr[x][e] < 0 || col[tr[x][e]]) {
if (tr[x][e] >= 0) {
forn (int, e1, 3) {
if (tr[tr[x][e]][e1] == x) {
tr[tr[x][e]][e1] = i - 1;
}
}
}
tr[i - 1][e] = tr[x][e];
tr[x][e] = i - 1;
tr[i - 1][e == 0 ? 1 : 0] = -2 - i;
tr[i - 1][e == 2 ? 1 : 2] = x;
l[i - 1] = tr[i - 1][0] < 0 ? -2 - tr[i - 1][0] : l[tr[i - 1][0]];
r[i - 1] = tr[i - 1][1] < 0 ? -2 - tr[i - 1][1] : r[tr[i - 1][1]];
break;
}
col[x] = true;
x = tr[x][e];
}
}
int r = 0;
while (tr[r][2] != -1) {
r = tr[r][2];
}
ans[n + r] = -1;
ansDfs(n, r);
out << "-1\n";
forn (int, i, 2 * n - 1) {
out << ans[i] << " ";
}
out << "\n";
}
int main() {
solve(cin, cout);
return 0;
}
example code (java)
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;
/**
* Built using CHelper plug-in
* Actual solution is at the top
*/
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
OutputWriter out = new OutputWriter(outputStream);
ForgottenTree solver = new ForgottenTree();
solver.solve(1, in, out);
out.close();
}
static class ForgottenTree {
public InputReader in;
public OutputWriter out;
public int nidx;
public int n;
public int[] par;
public void solve(int testNumber, InputReader in, OutputWriter out) {
this.in = in;
this.out = out;
n = in.nextInt();
nidx = n;
ForgottenTree.Node root = new ForgottenTree.Node(0);
ForgottenTree.Node.cgen = 0;
for (int i = 1; i < n; i++) {
ForgottenTree.Node.cgen++;
root.getLeaves();
root = insert(root, i);
}
out.println(-1);
par = new int[2 * n - 1];
dfs(root, -2);
out.println(par);
}
public String ask(int a, int b, int c) {
out.println((a + 1) + " " + (b + 1) + " " + (c + 1));
out.flush();
String ret = in.next();
if (ret.equals("-1")) System.exit(0);
return ret;
}
public void dfs(ForgottenTree.Node root, int p) {
par[root.label] = p + 1;
if (root.lchild != null) {
dfs(root.lchild, root.label);
dfs(root.rchild, root.label);
}
}
public ForgottenTree.Node insert(ForgottenTree.Node root, int label) {
if (!root.active()) {
return add(root, label);
}
root.dfs();
if (root.lchild == null) {
return add(root, label);
}
int curleaves = root.nleaves;
if (curleaves <= 1) {
int nnodes = 0;
ForgottenTree.Node cur = root;
while (!cur.isLeaf()) {
nnodes++;
if (cur.lchild.active()) cur = cur.lchild;
else cur = cur.rchild;
}
cur = root;
int depth = 0;
while (2 * (depth + 1) < nnodes) {
if (cur.lchild.active()) cur = cur.lchild;
else cur = cur.rchild;
depth++;
}
return process(root, cur, label);
}
ForgottenTree.Node cur = root;
while (true) {
if (cur.lchild == null) {
if (cur.par == null) {
return add(cur, label);
}
if (cur.which == 0) {
cur.par.setChild(0, add(cur, label));
return root;
} else {
cur.par.setChild(1, add(cur, label));
return root;
}
}
int x1 = cur.lchild.active() ? cur.lchild.nleaves : 0;
int x2 = cur.rchild.active() ? cur.rchild.nleaves : 0;
if (x1 * 2 > curleaves) {
cur = cur.lchild;
continue;
}
if (x2 * 2 > curleaves) {
cur = cur.rchild;
continue;
}
return process(root, cur, label);
}
}
public ForgottenTree.Node process(ForgottenTree.Node root, ForgottenTree.Node cur, int label) {
String s = ask(cur.x, cur.y, label);
switch (s) {
case "X":
if (cur.par == null) {
return add(cur, label);
}
cur.disable();
return insert(root, label);
case "Y":
cur.setChild(1, insert(cur.rchild, label));
return root;
case "Z":
cur.setChild(0, insert(cur.lchild, label));
return root;
default:
throw new RuntimeException();
}
}
public ForgottenTree.Node add(ForgottenTree.Node cnode, int label) {
ForgottenTree.Node add = new ForgottenTree.Node(nidx++);
add.setChild(0, cnode);
add.setChild(1, new ForgottenTree.Node(label));
return add;
}
static class Node {
public static int cgen;
public int x;
public int y;
public int label;
public int gen;
public int nleaves;
public int which;
public ForgottenTree.Node lchild;
public ForgottenTree.Node rchild;
public ForgottenTree.Node par;
public Node(int label) {
this.lchild = null;
this.rchild = null;
this.par = null;
this.which = 0;
this.label = label;
this.gen = 0;
this.nleaves = 1;
}
public boolean active() {
return gen < cgen;
}
public void disable() {
this.gen = cgen;
}
public boolean isLeaf() {
return lchild == null || (!lchild.active() && !rchild.active());
}
public void setChild(int which, ForgottenTree.Node x) {
if (which == 0) {
this.lchild = x;
} else {
this.rchild = x;
}
x.par = this;
x.which = which;
}
public void dfs() {
if (isLeaf()) {
this.nleaves = 1;
return;
}
this.nleaves = 0;
if (lchild.active()) {
lchild.dfs();
this.nleaves += lchild.nleaves;
}
if (rchild.active()) {
rchild.dfs();
this.nleaves += rchild.nleaves;
}
}
public void getLeaves() {
if (lchild == null) {
this.x = this.y = label;
return;
}
lchild.getLeaves();
rchild.getLeaves();
this.x = lchild.x;
this.y = rchild.x;
}
}
}
static class InputReader {
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
public InputReader(InputStream stream) {
this.stream = stream;
}
public int read() {
if (this.numChars == -1) {
throw new InputMismatchException();
} else {
if (this.curChar >= this.numChars) {
this.curChar = 0;
try {
this.numChars = this.stream.read(this.buf);
} catch (IOException var2) {
throw new InputMismatchException();
}
if (this.numChars <= 0) {
return -1;
}
}
return this.buf[this.curChar++];
}
}
public int nextInt() {
int c;
for (c = this.read(); isSpaceChar(c); c = this.read()) {
;
}
byte sgn = 1;
if (c == 45) {
sgn = -1;
c = this.read();
}
int res = 0;
while (c >= 48 && c <= 57) {
res *= 10;
res += c - 48;
c = this.read();
if (isSpaceChar(c)) {
return res * sgn;
}
}
throw new InputMismatchException();
}
public String next() {
int c;
while (isSpaceChar(c = this.read())) {
;
}
StringBuilder result = new StringBuilder();
result.appendCodePoint(c);
while (!isSpaceChar(c = this.read())) {
result.appendCodePoint(c);
}
return result.toString();
}
public static boolean isSpaceChar(int c) {
return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
}
}
static class OutputWriter {
private final PrintWriter writer;
public OutputWriter(OutputStream outputStream) {
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
}
public OutputWriter(Writer writer) {
this.writer = new PrintWriter(writer);
}
public void print(Object... objects) {
for (int i = 0; i < objects.length; i++) {
if (i != 0) {
writer.print(' ');
}
writer.print(objects[i]);
}
}
public void print(int[] array) {
for (int i = 0; i < array.length; i++) {
if (i != 0) {
writer.print(' ');
}
writer.print(array[i]);
}
}
public void println(int[] array) {
print(array);
writer.println();
}
public void println(Object... objects) {
print(objects);
writer.println();
}
public void close() {
writer.close();
}
public void flush() {
writer.flush();
}
public void println(int i) {
writer.println(i);
}
}
}
