UOJ Logo vfleaking的博客

博客

旷野大标程

2016-07-29 14:02:04 By vfleaking

标程大放送！

话说我监考时看到大部分人是手动 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;
}

评论

WrongAnswer
我考场就是用类似这样的写法，感觉挺方便的。 ```c++ int tot; int in(){ puts("I"); return ++tot; } int out(int i){ printf("O %d\n",i); return ++tot; } int add(int i,int j){ printf("+ %d %d\n",i,j); return ++tot; } // ... ``` 另外听说第7个点数据弱？
Sengxian
我有一个判断奇偶性的奇技淫巧。。。
dram
似乎 $s(x)-s'(x) = [s(x)]^2$。。但是误差好大。。。
CA
当时根本没写程序。。自己手算的
vanfleaking
woc。。第七个点居然是checker水。。我还以为是pretest水来让大家fst的【滑稽】

发表评论

可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。

Server time: 2024-11-27 10:30:37