标程大放送！
话说我监考时看到大部分人是手动 printf 和手算节点编号。。。好麻烦呀。。。
其实可以封装一下，重载下运算符，会爽很多，代码也更可读。
最后一个点， modmul 是可以获得满分的快速加，fastmodmul 是那个鬼畜的泰勒展开大法。注意用 modmul 已经能获得满分了，泰勒展开只是用来猎奇的。
说不定大家仔细研究标程然后发现标程错了，vfk你还我血汗分，还我血汗分！
#include "testlib.h"
#include <iostream>
#include <iomanip>
#include <vector>
#include <cassert>
using namespace std;
typedef long long int64;
int n = 0;
int opadd(int i, int j)
{
printf("+ %d %d\n", i, j);
return ++n;
}
int opneg(int i)
{
printf("- %d\n", i);
return ++n;
}
int opaddc(int i, string c)
{
printf("C %d %s\n", i, c.c_str());
return ++n;
}
int opshl(int i, int k)
{
printf("< %d %d\n", i, k);
return ++n;
}
int opshr(int i, int k)
{
printf("> %d %d\n", i, k);
return ++n;
}
int opsig(int i)
{
printf("S %d\n", i);
return ++n;
}
int n_in = 0;
int opin()
{
printf("I\n");
return ++n;
}
int opout(int i)
{
printf("O %d\n", i);
return ++n;
}
struct xvar
{
int id;
xvar() {}
xvar(const int &_id)
: id(_id) {}
friend inline xvar operator+(const xvar &lhs, const string &rhs)
{
return opaddc(lhs.id, rhs);
}
friend inline xvar operator+(const xvar &lhs, const xvar &rhs)
{
return opadd(lhs.id, rhs.id);
}
friend inline xvar operator<<(const xvar &lhs, const int &rhs)
{
return opshl(lhs.id, rhs);
}
friend inline xvar operator>>(const xvar &lhs, const int &rhs)
{
return opshr(lhs.id, rhs);
}
inline xvar operator-() const
{
return opneg(id);
}
};
inline xvar sig(xvar x)
{
return opsig(x.id);
}
inline xvar opout(xvar x)
{
opout(x.id);
return x;
}
inline string zeros(int n)
{
string s;
for (int i = 1; i <= n; i++)
s += '0';
return s;
}
inline string nines(int n)
{
string s;
for (int i = 1; i <= n; i++)
s += '9';
return s;
}
xvar psgn(xvar x)
{
return sig(x << 500);
}
xvar ge0(xvar x)
{
return psgn(x + ("0." + zeros(29) + "1"));
}
xvar ge1(xvar x)
{
return psgn(x + ("-0." + nines(30)));
}
xvar gt1(xvar x)
{
return psgn(x + ("-1." + zeros(29) + "1"));
}
xvar ncondx(xvar p, xvar x)
{
const int VL = 150;
p = p << (VL + 1);
xvar y = sig((x >> VL) + p);
return ((y + "-0.5") << (VL + 2)) + (-p);
}
xvar condx(xvar p, xvar x)
{
return ncondx(-p + "1", x);
}
xvar minx0(xvar x)
{
return ncondx(ge0(x), x);
}
xvar abs(xvar x)
{
const int VL = 150;
xvar p = ge0(x) << (VL + 2);
xvar y = sig((x >> VL) + p);
return x + ((-y + "0.5") << (VL + 3)) + p;
}
xvar land(xvar x, xvar y)
{
return gt1(x + y);
}
xvar lor(xvar x, xvar y)
{
return ge1(x + y);
}
xvar bits_to_x(xvar *bits)
{
xvar x = bits[0];
for (int i = 1; i < 32; i++)
x = (x << 1) + bits[i];
return x;
}
void x_to_bits(xvar x, xvar *bits)
{
x = x << 500;
long long t = 702955280397374434ll;
char ts[100];
for (int i = 31; i >= 1; i--)
{
sprintf(ts, "-%lld", t);
bits[i] = sig(x + (ts + zeros(142)));
x = x + -(bits[i] << (500 + i));
t /= 2;
}
bits[0] = x >> 500;
}
xvar sqr(xvar x)
{
const int UL = 130;
xvar dx = x >> UL;
xvar y = sig(dx + "-1.098612288668109691395245236922525704647490557822749451734694333637494293218608966873615754");
y = y + -((dx >> 4) + (dx >> 3));
// 1.31695789692481670862504634730796844402698197146751647976847225692046018541644397607421903
// - 0.25
// = 1.06695789692481670862504634730796844402698197146751647976847225692046018541644397607421903
return (sig(y + "1.06695789692481670862504634730796844402698197146751647976847225692046018541644397607421903") + "-0.788675134594812882254574390250978727823800875635063438009301163241988836151466672846857700") << (UL * 2 + 7);
}
void solve1()
{
xvar x1 = opin();
xvar x2 = opin();
opout(-((x1 + x2) << 1));
}
void solve2()
{
xvar x = opin();
opout(sig(-(x + (x << 4))));
}
void solve3()
{
opout((psgn(opin()) << 1) + "-1");
}
void solve4()
{
xvar x = opin();
opout(abs(x));
}
void solve5()
{
static xvar bits[32];
for (int i = 0; i < 32; i++)
bits[i] = opin();
opout(bits_to_x(bits));
}
void solve6()
{
xvar x = opin();
static xvar bits[32];
x_to_bits(x, bits);
for (int i = 31; i >= 0; i--)
opout(bits[i]);
}
void solve7()
{
xvar x = opin();
xvar y = opin();
xvar xbits[32], ybits[32];
x_to_bits(x, xbits);
x_to_bits(y, ybits);
xvar zbits[32];
for (int i = 0; i < 32; i++)
{
xvar s = xbits[i] + ybits[i];
zbits[31 - i] = s + -(psgn(s + "-1.5") << 1);
}
opout(bits_to_x(zbits));
}
void solve8()
{
xvar x = opin();
string alpha = "2.06343706889556054705";
string sigalpha = "0.887298334620741688550198422716226773933599412474263948504833186119911079463425709202638465";
opout((sig((x >> 200) + alpha) + ("-" + sigalpha)) << 200);
}
void solve9()
{
xvar x[17];
for (int i = 1; i <= 16; i++)
x[i] = opin();
for (int i = 1; i <= 16; i++)
for (int j = i + 1; j <= 16; j++)
{
xvar s = x[i] + x[j];
x[i] = x[i] + minx0(-x[i] + x[j]);
x[j] = s + -x[i];
}
for (int i = 1; i <= 16; i++)
opout(x[i]);
}
xvar modadd(xvar a, xvar b, xvar ma, xvar negm)
{
xvar s = a + b;
return s + ncondx(psgn(-s + ma), negm);
}
xvar modmul(xvar a, xvar b, xvar m, xvar negm)
{
xvar ta[32];
xvar tb[32];
x_to_bits(a, ta);
x_to_bits(b, tb);
xvar zero = a >> 1000;
xvar ma = m + "-0.1";
a = ta[31];
a = a + ncondx(psgn(-a + ma), negm);
for (int i = 30; i >= 0; i--)
{
a = a + a + ta[i];
a = a + ncondx(psgn(-a + ma), negm);
}
xvar res = zero;
res = condx(tb[0], a);
res = res + ncondx(psgn(-res + ma), negm);
a = a + a;
a = a + ncondx(psgn(-a + ma), negm);
for (int i = 1; i < 32; i++)
{
res = res + condx(tb[i], a);
res = res + ncondx(psgn(-res + ma), negm);
if (i < 31)
{
a = a + a;
a = a + ncondx(psgn(-a + ma), negm);
}
}
return res;
}
xvar fastmodmul(xvar a, xvar b, xvar m)
{
xvar ab = sqr(a + b);
ab = ab + -sqr(a);
ab = ab + -sqr(b);
ab = ab + "0.2";
ab = -ab;
ab = ab << 149;
for (int i = 63; i >= 0; i--)
{
const int VL = 300;
xvar mi = m << (150 + i);
xvar p = sig(mi + ab) << (VL + 1);
xvar y = sig((mi >> VL) + p);
ab = ab + ((y + "-0.5") << (VL + 2)) + -p;
}
ab = ab >> 150;
ab = -ab + "-0.1";
return ab;
}
void solve10()
{
xvar a = opin(), b = opin(), m = opin();
//opout(modmul(a, b, m, -m));
opout(fastmodmul(a, b, m));
}
int main(int argc, char **argv)
{
freopen("nodes1.out", "w", stdout);
n = 0, solve1();
freopen("nodes2.out", "w", stdout);
n = 0, solve2();
freopen("nodes3.out", "w", stdout);
n = 0, solve3();
freopen("nodes4.out", "w", stdout);
n = 0, solve4();
freopen("nodes5.out", "w", stdout);
n = 0, solve5();
freopen("nodes6.out", "w", stdout);
n = 0, solve6();
freopen("nodes7.out", "w", stdout);
n = 0, solve7();
freopen("nodes8.out", "w", stdout);
n = 0, solve8();
freopen("nodes9.out", "w", stdout);
n = 0, solve9();
freopen("nodes10.out", "w", stdout);
n = 0, solve10();
return 0;
}
鄂公网安备 42010202000505 号