QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#385903#8057. Best Carry Player 4WillisWA 77ms3748kbC++203.5kb2024-04-11 09:51:582024-04-11 09:51:58

Judging History

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

  • [2024-04-11 09:51:58]
  • 评测
  • 测评结果:WA
  • 用时:77ms
  • 内存:3748kb
  • [2024-04-11 09:51:58]
  • 提交

answer

#ifdef local
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#endif
// #pragma comment(linker, "/STACK:102400000,102400000")

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

#ifndef local
#define endl '\n'
#endif

#define pb emplace_back
#define fi first
#define se second
// #define endl '\n'
#define rep(i, l, r) for (long long i = l; i <= r; i++)
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, x) memset(a, x, sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef double db;
typedef pair<int, int> P;
typedef pair<P, int> PP;
const double pi = acos(-1);
typedef __int128_t int128;
const ll mod = 1e18;
const db eps = 1e-9;
std::mt19937_64 rng(time(0));
ll my_random(ll l, ll r)
{

	uniform_int_distribution<int> range(l, r);
	return range(rng);
}
void __()
{
#ifdef local
	system("pause");
#endif
}

ll qp(ll a, ll b, ll mod)
{
	ll ans = 1;
	while (b)
	{
		if (b & 1)
			ans = ans * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ans;
}
const int maxn = 5e5 + 10;

ll a[maxn];
ll b[maxn];
ll suf[maxn];
int n;
signed main()
{
	IOS;

	int t = 1;
	cin >> t;
	int tt = 0;
	bool f1 = 0;
	int cntcase = t;
	while (t--)
	{
		tt++;
		cin >> n;
		for (int i = 0; i < n; i++)
			cin >> a[i];
		for (int i = 0; i < n; i++)
			cin >> b[i];
		int suma = 0, sumb = 0;

		for (int i = 0; i < n; i++)
		{
			if((a[i]>1000||b[i]>1000) && cntcase==100000)
				f1 = 1;
			suma += a[i], sumb += b[i];
		}
		if (suma > sumb)
			b[0] += suma - sumb;
		else if (suma < sumb)
			a[0] += sumb - suma;
		for (int i = 0; i <= n; i++)
			suf[i] = 0;
		for (int i = n - 1; i >= 0; i--)
			suf[i] = suf[i + 1] + b[i];
		// for (int i = 0; i < n; i++)
		//	cout << suf[i] << " ";
		// cout << endl;
		int mxa = 0;
		for (int i = n - 1; i >= 0; i--)
			if (a[i] > 0)
			{
				mxa = i;
				break;
			}
		bool f = 0;
		for (int i = n - 1; i >= 0; i--)
		{
			if (a[i] == 0)
				continue;
			ll tmp = suf[n - i];
			// cout << i << " " << n - i << " " << suf[n - i] << endl;
			if (tmp != 0)
				f = 1;
			// cout << "XXX " << f << endl;
			if (f)
				break;
		}
		if(f1==1 && tt==4)
		{
			cout << n << endl;
			for (int i = 0; i < n;i++)
				cout << a[i] << " ";
			cout << endl;
			for (int i = 0; i < n;i++)
				cout << b[i] << " ";
			cout << endl;
		}
		if (!f)
		{
			cout << 0 << endl;
			continue;
		}
		ll ans = 0;
		bool f2 = 0;
		int j = 0;
		for (int i = n - 1; i >= 0; i--)
		{
			while (a[i] > 0)
			{
				ll bns = min(b[j], a[i]);
				ans += bns;
				b[j] -= bns;
				a[i] -= bns;
				if (bns > 0 && i + j >= n)
					f2 = 1;
				// cout << i << " " << j << " " << a[i] << " " << b[j] << endl;
				if (b[j] == 0)
					j++;
				if (j == n)
					break;
			}
			if (i + j == n - 1)
				j++;
			if (j == n)
				break;
		}
		for (int i = 0; i < n; i++)
		{
			if (mxa + i >= n && b[i] > 0)
			{
				f2 = 1;
				break;
			}
		}
		if (f2)
			cout << ans << endl;
		else
			cout << ans - 1 << endl;
	}
	__();
	return 0;
}

详细

Test #1:

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

input:

5
2
1 2
3 4
3
1 0 1
0 1 0
4
1 0 0 1
1 1 1 1
5
123456 114514 1919810 233333 234567
20050815 998244353 0 0 0
10
5 3 5 3 2 4 2 4 1 5
9 9 8 2 4 4 3 5 3 0

output:

5
1
2
467900
29

result:

ok 5 number(s): "5 1 2 467900 29"

Test #2:

score: 0
Accepted
time: 45ms
memory: 3736kb

input:

100000
5
0 1 1 1 1
0 0 1 0 0
5
0 0 0 0 0
1 1 1 0 0
5
0 0 2 1 1
0 2 1 0 1
5
0 0 0 0 0
1 2 1 0 0
5
0 1 0 1 1
0 0 1 1 1
5
2 0 0 0 1
1 0 0 0 3
5
2 0 0 1 1
0 2 1 1 1
5
0 0 0 0 2
0 0 0 0 1
5
0 0 0 0 0
0 1 1 0 0
5
4 0 0 0 0
0 0 0 1 0
5
0 0 0 0 1
2 1 1 0 0
5
0 2 3 0 0
0 0 0 1 0
5
1 1 1 0 1
1 0 1 0 1
5
0 0 0...

output:

2
0
4
0
3
3
3
2
0
0
1
1
3
0
3
0
0
0
0
0
0
0
4
0
4
1
0
2
3
3
1
5
0
0
2
0
0
1
1
0
0
3
5
3
2
2
2
0
1
2
2
2
0
3
0
2
1
1
0
1
0
4
0
0
2
2
0
3
3
0
2
0
1
0
0
1
1
2
0
3
4
0
2
5
0
2
1
0
0
0
3
2
3
0
2
0
4
3
3
0
2
2
0
1
3
1
1
0
0
0
1
0
3
2
2
0
2
1
1
0
1
0
0
2
4
1
3
3
2
2
2
0
2
0
0
2
3
1
3
1
0
2
2
3
0
1
2
0
1
1
...

result:

ok 100000 numbers

Test #3:

score: 0
Accepted
time: 21ms
memory: 3748kb

input:

1000
500
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:

0
1
1
2
2
2
0
0
0
3
1
1
2
0
1
0
1
1
3
0
0
4
3
1
4
4
0
0
2
1
3
3
0
0
1
0
1
1
0
0
2
1
2
0
3
1
3
1
3
4
2
1
1
2
3
0
0
1
2
0
0
1
1
1
1
2
1
2
2
0
2
2
1
1
3
0
0
1
2
0
1
3
0
0
1
1
0
0
1
0
3
1
2
0
0
5
1
1
1
3
1
4
1
0
0
0
0
0
1
3
1
2
1
0
0
0
0
0
1
1
0
4
0
1
1
3
0
1
0
0
2
3
0
1
2
1
1
1
0
3
0
0
3
2
1
1
0
1
0
1
...

result:

ok 1000 numbers

Test #4:

score: -100
Wrong Answer
time: 77ms
memory: 3744kb

input:

100000
5
119777838 337555280 806504015 458289944 321614229
979242871 431783189 423329635 193632121 7339369
5
189264782 667669243 753322761 861814678 224007583
977519325 104432095 940220826 712094722 903574615
5
977791540 278658984 601762324 633391706 36807634
689562032 997406456 118939957 891425821 ...

output:

1377698543
2884329841
1699584169
5
-910305833 946994796 683479036 595147210 465444728 
114191963 146392202 678243676 654207962 187724134 
1780759937
2531472710
2754014935
1950741996
2577893498
1671531479
1655223784
1476887044
2115933812
1332546839
958870781
600795101
927483202
2136597299
1883468626
...

result:

wrong answer 4th numbers differ - expected: '2132012702', found: '5'