QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#524510#6770. AntsPonyHexWA 278ms20444kbC++147.0kb2024-08-19 18:44:092024-08-19 18:44:09

Judging History

This is the latest submission verdict.

  • [2024-08-19 18:44:09]
  • Judged
  • Verdict: WA
  • Time: 278ms
  • Memory: 20444kb
  • [2024-08-19 18:44:09]
  • Submitted

answer

#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
using namespace std;
#define ll long long
#define lc u<<1
#define rc u<<1|1
#define X first
#define Y second
const int N = 1e5 + 5;
const int M = 5005;
const ll maxm = 1e18 + 5;

struct node {
    ll pos, state;
};
vector<node>mp;
ll ans = 0;

int cmp(node a, node b) {
    if (a.pos < b.pos)return 1;
    return 0;
}

ll R = 1e9 + 1;

void solve()
{
    //再战ant,思路没有问题,先按周期走,然后
    //懂了,还是距离的问题,越是到最后,越不能急,写的时候急
    //写完了,就应该仔细考究
    //模拟过程并不可取
    //仅在一次循环的时候才需要模拟
    ll n, l, r; cin >> n >> l >> r;
    //一个周期,我认为是左右,都减
    ll ans = 0;
    ll round = (min(l, r) / n);//当一端出现缺口,我们进行两次大循环模拟即可
    //我们认为一次大循环指的是所有的向右走的都撞了右壁,所有的向左走的都撞了左壁
    //一轮round指的是所有节点左撞一次右撞一次回到原点的过程
    ans += R * round * 2;
    l -= round * n; r -= round * n;
    //先让左走全撞,右走全撞
    //我缺乏快速切题的能力,我是说难题
    for (int i = 0; i < n; i++) {
        ll val; cin >> val;
        mp.push_back({ val,i });
    }
    for (int i = 0; i < n; i++) {
        cin >> mp[i].state;
    }
    //我明明就想要继续写,然后上蓝,然后挂头像,继续

    sort(mp.begin(), mp.end(), cmp);
    ll mx = 0;//记录移动的最大步数,障碍物其实是放置在0和1e9+1的位置上,如果有墙就返回,无走到那里就判定为掉下去
    for (int i = 0; i < n; i++) {
        //if (mp[i].state != 0)break;//让所有左走的都撞
        if (mp[i].state == 0) {
            if (l) {
                l--;
                mx = max(mp[i].pos, mx);
            }
            else {
                mp[i].state = 77;
                mx = max(mp[i].pos, mx);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        if (mp[i].state == 1) {
            if (r) {
                r--;
                mx = max(R - mp[i].pos, mx);
            }
            else {
                mp[i].state = 77;
                mx = max(R - mp[i].pos, mx);
            }
        }
    }
    ans += mx;
    for (int i = 0; i < n; i++) {
        if (mp[i].state == 0) {
            mp[i].state = 1;
            //左走先走到0然后右走
            mp[i].pos = (mx - mp[i].pos);
        }
        else if (mp[i].state == 1) {
            mp[i].state = 0;
            mp[i].pos = R - (mx - (R - mp[i].pos));
        }
    }
    //更新状态再走一次
    /*
    cout << ans << endl;
    for (int i = 0; i < n; i++) {
        cout << mp[i].pos << " " << mp[i].state << endl;
    }*/


    sort(mp.begin(), mp.end(), cmp);
    mx = 0;//记录移动的最大步数,障碍物其实是放置在0和1e9+1的位置上,如果有墙就返回,无走到那里就判定为掉下去
    for (int i = 0; i < n; i++) {
        //if (mp[i].state != 0)break;//让所有左走的都撞
        if (mp[i].state == 0) {
            if (l) {
                l--;
                mx = max(mp[i].pos, mx);
            }
            else {
                mp[i].state = 77;
                mx = max(mp[i].pos, mx);
            }
        }
    }
    for (int i = n-1; i>=0; i--) {
        if (mp[i].state == 1) {
            if (r) {
                r--;
                mx = max(R - mp[i].pos, mx);
            }
            else {
                mp[i].state = 77;
                mx = max(R - mp[i].pos, mx);
            }
        }
    }
    ans += mx;
    for (int i = 0; i < n; i++) {
        if (mp[i].state == 0) {
            mp[i].state = 1;
            //左走先走到0然后右走
            mp[i].pos = (mx - mp[i].pos);
        }
        else if (mp[i].state == 1) {
            mp[i].state = 0;
            mp[i].pos = R - (mx - (R - mp[i].pos));
        }
    }
    //更新状态再走一次
    /*
    cout << ans << endl;
    for (int i = 0; i < n; i++) {
        cout << mp[i].pos << " " << mp[i].state << endl;
    }*/

    sort(mp.begin(), mp.end(), cmp);
    mx = 0;//记录移动的最大步数,障碍物其实是放置在0和1e9+1的位置上,如果有墙就返回,无走到那里就判定为掉下去
    for (int i = 0; i < n; i++) {
        //if (mp[i].state != 0)break;//让所有左走的都撞
        if (mp[i].state == 0) {
            if (l) {
                l--;
                mx = max(mp[i].pos, mx);
            }
            else {
                mp[i].state = 77;
                mx = max(mp[i].pos, mx);
            }
        }
    }
    for (int i = n-1; i>=0; i--) {
        if (mp[i].state == 1) {
            if (r) {
                r--;
                mx = max(R - mp[i].pos, mx);
            }
            else {
                mp[i].state = 77;
                mx = max(R - mp[i].pos, mx);
            }
        }
    }
    ans += mx;
    for (int i = 0; i < n; i++) {
        if (mp[i].state == 0) {
            mp[i].state = 1;
            //左走先走到0然后右走
            mp[i].pos = (mx - mp[i].pos);
        }
        else if (mp[i].state == 1) {
            mp[i].state = 0;
            mp[i].pos = R - (mx - (R - mp[i].pos));
        }
    }
    //更新状态再走一次
    //cout << ans << endl;

    sort(mp.begin(), mp.end(), cmp);
    mx = 0;
    for (int i = 0; i < n; i++) {
        //if (mp[i].state != 0)break;//让所有左走的都撞
        if (mp[i].state == 0) {
            if (l) {
                l--;
                mx = max(mp[i].pos, mx);
            }
            else {
                mp[i].state = 77;
                mx = max(mp[i].pos, mx);
            }
        }
    }
    for (int i = 0; i>=0; i--) {
        if (mp[i].state == 1) {
            if (r) {
                r--;
                mx = max(R - mp[i].pos, mx);
            }
            else {
                mp[i].state = 77;
                mx = max(R - mp[i].pos, mx);
            }
        }
    }
    ans += mx;
    for (int i = 0; i < n; i++) {
        if (mp[i].state == 0) {
            mp[i].state = 1;
            //左走先走到0然后右走
            mp[i].pos = (mx - mp[i].pos);
        }
        else if (mp[i].state == 1) {
            mp[i].state = 0;
            mp[i].pos = R - (mx - (R - mp[i].pos));
        }
    }
    //更新状态再走一次


    cout << ans << endl;
    return;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    //std::cin >> T;
    while (T--)
        solve();
    return 0;
}

ll ksm(ll a, ll b) {
    ll base = a;
    ll ans = 1;
    while (b) {
        if (b & 1)ans *= base;
        base *= base;
        b >>= 1;
    }
    return ans;
}
ll gcd(ll a, ll b) {
    return b ? gcd(b, a % b) : a;
}
/*致我已死的友人*/
/*PonyHex*/

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3688kb

input:

2 2 4
2 3
0 1

output:

4000000001

result:

ok single line: '4000000001'

Test #2:

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

input:

1 1000000000 1000000000
500000000
0

output:

2000000002500000000

result:

ok single line: '2000000002500000000'

Test #3:

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

input:

1 1000000000 500000000
500000000
1

output:

1000000001500000001

result:

ok single line: '1000000001500000001'

Test #4:

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

input:

1 500000000 1000000000
500000000
0

output:

1000000001500000000

result:

ok single line: '1000000001500000000'

Test #5:

score: -100
Wrong Answer
time: 278ms
memory: 20444kb

input:

999963 1000000000 1000000000
516 793 2609 2721 3010 3378 4494 6294 7719 9298 9582 10021 10255 13552 16357 16771 16864 18824 19006 19162 19583 22099 22970 23637 25760 26962 29349 31140 34093 34398 35622 35765 35868 35899 36213 37137 38062 43181 43361 44347 46328 48145 48188 49187 50303 50873 52999 53...

output:

2002000001486

result:

wrong answer 1st lines differ - expected: '2001074431727', found: '2002000001486'