QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#379077#6692. Building CompanyasaltfishWA 0ms13136kbC++202.6kb2024-04-06 16:07:052024-04-06 16:07:05

Judging History

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

  • [2024-04-06 16:07:05]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:13136kb
  • [2024-04-06 16:07:05]
  • 提交

answer

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string.h>
#include<iomanip>
#include<stack>
#include<deque>
#include<queue>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
inline int read() {
	register int s = 0, w = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-')
			w = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9')
		s = s * 10 + ch - '0', ch = getchar();
	return s * w;
}
struct jh
{
	map<ll, ll>d, f;
}l[100005];
ll n, g, nu;
map<ll, ll>h,kl;
int cmp(jh a, jh b)
{
	for (auto i : kl)
	{
		ll p = i.first;
		if ((!a.d.count(p) && b.d.count(p)) || (a.d.count(p) && b.d.count(p) && a.d[p] < b.d[p]))
		{
			return 1;
		}
		else if ((a.d.count(p) && !b.d.count(p)) || (a.d.count(p) && b.d.count(p) && a.d[p] > b.d[p]))
			return 0;
	}
	return 1;
}
//vector<map<ll, ll>>d[100005];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	nu = read();
	ll p, sh;
	for (int i = 1; i <= nu; i++)
	{
		p = read(), sh = read();
		h[p] = sh;
	}
	n = read();
	for (int i = 1; i <= n; i++)
	{
		nu = read();
		for (int y = 1; y <= nu; y++)
		{
			p = read(), sh = read();
			l[i].d[p] = sh;
			kl[p]++;
		}
		nu = read();
		for (int y = 1; y <= nu; y++)
		{
			p = read(), sh = read();
			l[i].f[p] = sh;
		}
	}
	sort(l + 1, l + n + 1, cmp);
	g = 0; ll k = 0;
	map<ll, ll>hf;
	//for (int i = 1; i <= n; i++)
	//{
	//	cout << l[i].d.size() << " ";
	//	for(auto y:l[i].d)
	//	cout <<y.first<<" " << y.second << " ";
	//	cout << '\n';
	//}
	while (1)
	{
		map<ll, ll>pl;
		ll bee=0, enn=n;
		//cout << h.size() <<" ";
		//for (auto i : h)
		//{
		//	cout << i.first << " " << i.second << " ";
		//}
		//cout << '\n';
		for (auto i : h)
		{
			ll be = bee, en = enn, mid,op=i.first;
			while (en > be)
			{
				mid = (be + en+1) / 2;
				//cout << l[mid].d[op] << "      ";
				if (!l[mid].d.count(op) || l[mid].d[op] <= h[op])be = mid;
				else en = mid-1;
			}
			enn = be;
			if (enn == 0)
			{
				enn = -1; break;
			}
			if (bee > enn)
			{
				break;
			}
			for (int y = 1; y <= enn; y++)
			{
				if(l[y].d.count(op))
				pl[y]++;
			}
		}
		//for (auto i : hf)cout << i.first << " ";
		//cout << '\n';
		if (k == n || enn <=bee)
		{
			break;
		}
		int opp = 0;
		for (int i = 1; i <= enn; i++)
		{
			if (!hf.count(i)&&pl[i]==l[i].d.size())
			{
				hf[i]++;
				for (auto y : l[i].f)
				{
					h[y.first] += y.second;
				}
				k++;
				opp++;
			}
		}
		if (opp == 0)break;
		enn = n;
	}
	printf("%lld", k);
	return 0;
}

詳細信息

Test #1:

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

input:

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

output:

4

result:

ok 1 number(s): "4"

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 13136kb

input:

3 610031727 590328742 816793299 18485566 654221125 47823436
10
3 610031727 224714165 816793299 491951703 654221125 593479446
1 610031727 538596643
1 610031727 551036304
3 816793299 262985484 610031727 52580932 654221125 424397787
1 654221125 889197190
3 654221125 126924193 610031727 963399336 816793...

output:

1

result:

wrong answer 1st numbers differ - expected: '10', found: '1'