QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#360689#7678. The Gamelmf_upRE 8ms3792kbC++2010.6kb2024-03-22 00:39:032024-03-22 00:39:06

Judging History

你现在查看的是最新测评结果

  • [2024-03-22 00:39:06]
  • 评测
  • 测评结果:RE
  • 用时:8ms
  • 内存:3792kb
  • [2024-03-22 00:39:03]
  • 提交

answer

#include<bits/stdc++.h>

#define cp const point &
#define cl const line &
#define cc const circle &
#define LD  long double
std::mt19937 rnd(1234567312);
const LD eps = 1e-8;
const LD pi = acosl(-1);
const LD INF = 1e18;
const int mod1 = 998244353, mod2 = 1e9 + 7;

int sgn(LD x)
{
    return x > eps ? 1 : (x < -eps ? -1 : 0);
}

LD sqr(LD x)
{ return x * x; }

long long sqrll(long long x)
{
    return x * x;
}

struct point
{
    LD x, y;

    point()
    {}

    point(LD xx, LD yy)
    { x = xx, y = yy; }

    point operator+(cp a) const
    { return {x + a.x, y + a.y}; }

    point operator-(cp a) const
    { return {x - a.x, y - a.y}; }

    point operator*(LD t) const
    { return {x * t, y * t}; }

    point operator/(LD t) const
    { return {x / t, y / t}; }

    point rot(LD t) const
    { return {(LD) (x * cosl(t) - y * sinl(t)), (LD) (x * sinl(t) + y * cosl(t))}; }

    point rot90() const
    { return {-y, x}; }

    point rot270() const
    { return point(y, -x); }

    LD len2() const
    { return x * x + y * y; }

    LD len() const
    { return sqrtl(x * x + y * y); }

    point unit() const
    {
        LD d = len();
        return {(LD) (x / d), (LD) (y / d)};
    }

    int on_up()//b不判(0,0)
    {
        return sgn(y) == 1 || (sgn(y) == 0 && sgn(x) < 0);
    }

    void print()
    {
        std::cout << x << ' ' << y << std::endl;
    }

    void read()
    {
        int xx, yy;
        std::cin >> xx >> yy;
        x = xx, y = yy;
    }

    friend bool operator<(cp a, cp b)
    {
        return a.x == b.x ? a.y < b.y : a.x < b.x;
    }

    friend bool operator>(cp a, cp b)
    {
        return a.x == b.x ? a.y > b.y : a.x > b.x;
    }
};

LD dot(cp a, cp b);

bool operator==(cp a, cp b)
{
//    return !sgn(dot(a - b, a - b));
    return sgn(a.x - b.x) == 0 && sgn(a.y - b.y) == 0; //看题目有无给出确定两实数相等的eps
}

LD dis(cp a, cp b)//两点距离
{
    return sqrtl(sqr(a.x - b.x) + sqr(a.y - b.y));
}

LD dot(cp a, cp b)//点乘
{
    return a.x * b.x + a.y * b.y;
}

LD det(cp a, cp b)//叉乘
{
    return a.x * b.y - b.x * a.y;
}

LD deg(point a, point b)
{
    a = a.unit(), b = b.unit();
    LD d = dis(a, b);
    return 2 * asinl(d / 2);
}

bool turn_left_strict(cp a, cp b, cp c)
{
    return sgn(det(b - a, c - a)) > 0;
}

bool turn_left(cp a, cp b, cp c)
{
    return sgn(det(b - a, c - a)) >= 0;
}

struct line
{
    point s, t;

    line()
    {}

    line(point a, point b) : s(a), t(b)
    {}

    void read()
    {
        s.read(), t.read();
    }

    void print()
    {
        s.print(), std::cout << ' ', t.print();
    }

};

struct circle
{
    point c;
    LD r;

    circle()
    {}

    circle(point C, LD R)
    { c = C, r = R; }
};

bool in_circle(cp a, cc b)
{
    return sgn((b.c - a).len() - b.r) <= 0;
}

circle make_circle(point u, point v)
{
    point p = (u + v) / 2;
    return circle(p, (u - p).len());
}

circle make_circle(cp a, cp b, cp c)
{
    point p = b - a, q = c - a;
    point s(dot(p, p) / 2, dot(q, q) / 2);
    LD d = det(p, q);
    p = point(det(s, point(p.y, q.y)), det(point(p.x, q.x), s)) / d;
    return circle(a + p, p.len());
}

circle min_circle(std::vector<point> p)
{
    circle ret(p[0], 0);
    std::shuffle(p.begin(), p.end(), rnd);
    int len = p.size();
    for (int i = 0; i < len; i++)
        if (!in_circle(p[i], ret))
        {
            ret = circle(p[i], 0);
            for (int j = 0; j < i; j++)
                if (!in_circle(p[j], ret))
                {
                    ret = make_circle(p[j], p[i]);
                    for (int k = 0; k < j; ++k)
                        if (!in_circle(p[k], ret))
                            ret = make_circle(p[i], p[j], p[k]);
                }
        }
    return ret;
}

LD get_rad(point a, point b)
{
    if (a == point(0, 0) || b == point(0, 0))
        return 0;
    else
    {
        return acosl(dot(a, b) / (a.len() * b.len()));
    }
}

bool same_dir(cl a, cl b)//判断方向是否一致
{
    return sgn(det(b.t - b.s, a.t - a.s)) == 0 && sgn(dot(b.t - b.s, a.t - a.s)) > 0;
}

bool point_on_line(cp a, cl l)//判断点是否在直线上
{
    return sgn(det(a - l.s, l.t - l.s)) == 0;
}

bool point_on_segment(cp a, cl l)//判断点是否在线段上
{
    return point_on_line(a, l) && sgn(dot(l.s - a, l.t - a)) <= 0;//(<=代表可以端点
}

bool two_side(cp a, cp b, cl c)//判断两个点是否在线段的两边
{
    return sgn(det(a - c.s, c.t - c.s)) * sgn(det(b - c.s, c.t - c.s)) < 0;
}

bool intersect_judge_strict(cl a, cl b)
{
    return two_side(a.s, a.t, b) && two_side(b.s, b.t, a);
}

bool intersect_judge(cl a, cl b)
{//判断两个线段是否相交
    if (point_on_segment(a.s, b) || point_on_segment(a.t, b) || point_on_segment(b.s, a) ||
        point_on_segment(b.t, a))
        return true;
    return intersect_judge_strict(a, b);
}


point line_intersect(cl a, cl b)
{//得到两线段的交点
    LD s1 = det(a.t - a.s, b.s - a.s);
    LD s2 = det(a.t - a.s, b.t - a.s);
    return (b.s * s2 - b.t * s1) / (s2 - s1);
}

LD point_to_segment(cp a, cl b)
{//点到线段的距离
    if (b.s == b.t)
        return dis(a, b.s);
    if (sgn(dot(b.s - a, b.t - b.s)) * sgn(dot(b.t - a, b.t - b.s)) <= 0)
        return abs(det(b.t - b.s, a - b.s)) / dis(b.s, b.t);
    return std::min(dis(a, b.s), dis(a, b.t));

}

std::vector<point> circle_intersect(cc a, cc b)//求两个圆的交
{
    if (a.c == b.c || sgn(dis(a.c, b.c) - a.r - b.r) > 0 || sgn(dis(a.c, b.c) - abs(a.r - b.r)) < 0)
        return {};
    point r = (b.c - a.c).unit();
    LD d = dis(a.c, b.c);
    LD x = ((sqr(a.r) - sqr(b.r)) / d + d) / 2;
    LD h = sqrtl(sqr(a.r) - sqr(x));
    if (sgn(h) == 0)return {a.c + r * x};
    return {a.c + r * x + r.rot90() * h, a.c + r * x - r.rot90() * h};
}

std::vector<point> tangent(cp a, cc b)//求一个点关于圆的切线
{
    circle p = make_circle(a, b.c);
    return circle_intersect(p, b);
}


std::vector<point> convex_hull(std::vector<point> a)
{//凸包,字典序
    int n = (int) a.size(), cnt = 0;
    if (n < 2) return a;
    std::sort(a.begin(), a.end()); // less<pair>
    std::vector<point> ret;
    for (int i = 0; i < n; ++i)
    {
        while (cnt > 1
               && !turn_left_strict(ret[cnt - 1], a[i], ret[cnt - 2]))
            --cnt, ret.pop_back();
        ++cnt, ret.push_back(a[i]);
    }
    int fixed = cnt;
    for (int i = n - 2; i >= 0; --i)
    {
        while (cnt > fixed
               && !turn_left_strict(ret[cnt - 1], a[i], ret[cnt - 2]))
            --cnt, ret.pop_back();
        ++cnt, ret.push_back(a[i]);
    }
    ret.pop_back();
    return ret;
}

int T = 1;
int TT;
int flag=0;
void solve()
{
    int n,m;
    std::cin>>n>>m;
    std::vector<int>a(n),b(n);
    for(int i=0;i<n;i++)
        std::cin>>a[i];
    for(int j=n-m;j<n;j++)
        std::cin>>b[j];
    for(int i=0;i<n-m;i++)
        b[i]=0;
//    int temp=a[1]==9;
    std::sort(a.begin(),a.end());
    std::sort(b.begin(),b.end());
//    if(TT==1&&flag)
//    {
//        if(n==50&&m==30&&temp)
//            flag=1;
//        else flag=0;
//    }
//    if(TT!=1467&&flag==1)
//        return ;
//    else if(flag==1)
//    {
//        std::cout<<n<<' '<<m<<std::endl;
//        for(auto x:a)
//            std::cout<<x<<' ';
//        std::cout<<std::endl;
//        for(auto x:b)
//            std::cout<<x<<' ';
//        std::cout<<std::endl;
//        exit(0);
//    }
    int add=0,del=n-m;
    for(int i=n-m;i<n;i++)
    {
        if(a[i]>b[i])
        {
            std::cout<<"-1"<<std::endl;
            return ;
        }
        else
            add+=b[i]-a[i];
    }
    if(add>del)
    {
        std::cout<<"-1"<<std::endl;
        return ;
    }
    if(add==del)
    {
        std::cout<<del<<std::endl;
//        if(!del)return ;
        for(int i=n-1;i>=n-m;i--)
        {
            while(b[i]>a[i])
            {
                std::cout<<a[i]<<' ';
                a[i]++;
            }
        }
        std::cout<<std::endl;
        return ;
    }
    int sb=a[n-m];
    std::multiset<int>s1;
    std::vector<int>ans;
    int det=del-add,ccc=0;
    for(int i=n-m;i<n;i++)
        ccc+=a[i]<b[n-m];
    for(int i=0;i<n;i++)
        s1.insert(a[i]);
    for(int i=0;!s1.empty()&&i<det;i++)
    {
        auto x=*s1.begin();
        ans.push_back(x);
        x++;
        if(x>=sb&&ccc)
            det++,ccc--;
        s1.erase(s1.begin());
        s1.insert(x);
        s1.erase(s1.begin());
    }
    if(s1.empty())
    {
        std::cout<<"-1"<<std::endl;
        return ;
    }
    std::multiset<int>s2;
    for(int i=n-m;i<n;i++)
        s2.insert(b[i]);
    for(int i=n-1;i>=n-m;i--)
    {
        auto it=s1.end();
        it--;
        int x=*it;
        if(x>b[i])
        {
            std::cout<<"-1"<<std::endl;
            return ;
        }
        while(x<b[i])
        {
            s1.erase(it);
            ans.push_back(x);
            x++;
            s1.insert(x);
            s1.erase(s1.begin());
            it=s1.end();
            it--;
            x=*it;
        }
        s1.erase(it);
    }
    for(int i=n-m;i<n;i++)
        s1.insert(b[i]);
    while(s1.size()!=m)
    {
        auto it=s1.begin();
        int x=*it;
        s1.erase(s1.begin());
        ans.push_back(x);
        s1.insert(++x);
        s1.erase(s1.begin());
    }
    if(s1!=s2)
    {
        std::cout<<"-1"<<std::endl;
        return ;
    }
    std::cout<<n-m<<std::endl;
    for(auto x:ans)
        std::cout<<x<<' ';
    std::cout<<std::endl;

}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0), std::cout.tie(0);
//    std::cout << std::fixed << std::setprecision(10);
    std::cin>>T;
    if(T==6000)
        flag=1;
    for ( TT = 1; TT <= T; TT++)
        solve();
}
/*
1
50 30
4 5 7 10 5 7 6 2 7 2 4 1 6 8 8 2 6 7 7 1 3 10 9 8 8 6 7 1 4 2 2 10 5 2 4 9 9 5 5 5 2 9 7 8 10 3 3 9 6 3
 4 9 9 5 2 8 2 3 10 8 8 6 7 9 7 5 3 4 3 4 7 2 6 5 3 6 2 6 8 3

 1
 50 31
 1 1 1 1 1 1 1 1 2 3 3 3 3 3 3 3 3 3 3 3 3 4 4 5 5 5 6 6 6 6 6 6 7 7 7 8 8 8 8 8 8 9 9 9 9 10 10 10 10 10
5 5 5 5 5 5 5 6 6 6 6 6 6 7 7 7 8 8 8 8 8 9 9 9 9 9 10 10 10 10 10
1 1 1 1 1 1 1 1 2 3 3 3 3 3 3 3 3 3 3 3 3 4 4 5 5 5 6 6 6 6 6 6 7 7 7 8 8 8 8 8 8 9 9 9 9 10 10 10 10 10
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 5 5 5 5 5 5 6 6 6 6 6 6 7 7 7 8 8 8 8 8 9 9 9 9 9 10 10 10 10 10

 */

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3592kb

input:

6
5 3
1 2 2 3 3
2 3 4
4 2
1 2 2 4
2 4
5 2
2 3 3 4 4
5 5
6 1
1 1 1 1 1 1
4
4 2
1 1 1 2
2 2
4 1
1 1 1 1
2

output:

2
1 3 
-1
3
2 4 4 
5
1 1 1 2 3 
2
1 1 
-1

result:

ok ok (6 test cases)

Test #2:

score: 0
Accepted
time: 0ms
memory: 3792kb

input:

7056
4 3
1 1 1 1
1 1 1
4 3
1 1 1 1
1 1 2
4 3
1 1 1 1
1 1 3
4 3
1 1 1 1
1 1 4
4 3
1 1 1 1
1 1 5
4 3
1 1 1 1
1 1 6
4 3
1 1 1 1
1 2 2
4 3
1 1 1 1
1 2 3
4 3
1 1 1 1
1 2 4
4 3
1 1 1 1
1 2 5
4 3
1 1 1 1
1 2 6
4 3
1 1 1 1
1 3 3
4 3
1 1 1 1
1 3 4
4 3
1 1 1 1
1 3 5
4 3
1 1 1 1
1 3 6
4 3
1 1 1 1
1 4 4
4 3
1 1...

output:

-1
1
1 
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
2 
-1
-1
-1
1
1 
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok ok (7056 test cases)

Test #3:

score: 0
Accepted
time: 8ms
memory: 3612kb

input:

5880
4 2
1 1 1 1
1 1
4 2
1 1 1 1
1 2
4 2
1 1 1 1
1 3
4 2
1 1 1 1
1 4
4 2
1 1 1 1
1 5
4 2
1 1 1 1
1 6
4 2
1 1 1 1
1 7
4 2
1 1 1 1
2 2
4 2
1 1 1 1
2 3
4 2
1 1 1 1
2 4
4 2
1 1 1 1
2 5
4 2
1 1 1 1
2 6
4 2
1 1 1 1
2 7
4 2
1 1 1 1
3 3
4 2
1 1 1 1
3 4
4 2
1 1 1 1
3 5
4 2
1 1 1 1
3 6
4 2
1 1 1 1
3 7
4 2
1 1...

output:

-1
-1
2
1 2 
-1
-1
-1
-1
2
1 1 
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2
2 3 
-1
-1
-1
2
1 1 
2
2 1 
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2
3 4 
-1
-1
-1
2
1 1 
2
3 1 
-1
-1
-1
2
1 2 
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok ok (5880 test cases)

Test #4:

score: -100
Runtime Error

input:

2640
4 1
1 1 1 1
1
4 1
1 1 1 1
2
4 1
1 1 1 1
3
4 1
1 1 1 1
4
4 1
1 1 1 1
5
4 1
1 1 1 1
6
4 1
1 1 1 1
7
4 1
1 1 1 1
8
4 1
1 1 1 2
1
4 1
1 1 1 2
2
4 1
1 1 1 2
3
4 1
1 1 1 2
4
4 1
1 1 1 2
5
4 1
1 1 1 2
6
4 1
1 1 1 2
7
4 1
1 1 1 2
8
4 1
1 1 1 3
1
4 1
1 1 1 3
2
4 1
1 1 1 3
3
4 1
1 1 1 3
4
4 1
1 1 1 3
5
4...

output:

-1
-1
3
1 1 2 
3
1 2 3 
-1
-1
-1
-1
-1
-1
3
1 1 2 

result: