QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#185836#7064. Spy0x4F5DA2WA 3ms5372kbC++143.6kb2023-09-22 17:23:242023-09-22 17:23:24

Judging History

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

  • [2023-09-22 17:23:24]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:5372kb
  • [2023-09-22 17:23:24]
  • 提交

answer

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <limits>

using namespace std;

const int maxn = 400;
int n;
struct AmyNode{
	long long a;
	int p;
}Amy[maxn + 10];
long long sum[maxn + 10];
bool cmp(AmyNode a, AmyNode b){
	return a.a < b.a;
}

long long b[maxn + 10];
long long c[maxn + 10];

long long getE(long long x){
	int l = 0, r = n;
	while(l != r){
		int mid = (l + r + 1) >> 1;
		if(Amy[mid].a < x)
			l = mid;
		else
			r = mid - 1;
	}
	return sum[l];
}

template<typename T>
struct hungarian {
	int n;
	vector<int> matchx;
	vector<int> matchy;
	vector<int> pre;
	vector<bool> visx;
	vector<bool> visy;
	vector<T> lx;
	vector<T> ly;
	vector< vector<T> >g;
	vector<T> slack;
	T inf;
	T res;
	queue<int> q;
	int org_n;
	int org_m;
	
	hungarian(int _n, int _m){
		org_n = _n;
		org_m = _m;
		n = max(_n, _m);
		inf = numeric_limits<T>::max();
		res = 0;
		g = vector<vector<T> >(n, vector<T>(n));
		matchx = vector<int>(n, -1);
		matchy = vector<int>(n, -1);
		pre = vector<int>(n);
		visx = vector<bool>(n);
		visy = vector<bool>(n);
		lx = vector<T>(n, -inf);
		ly = vector<T>(n);
		slack = vector<T>(n);
	}
	
	void addEdge(int u, int v, T w){
		g[u][v] = max(w, (T)0);
	}
	
	bool check(int v){
		visy[v] = true;
		if(matchy[v] != -1){
			q.push(matchy[v]);
			visx[matchy[v]] = true;
			return false;
		}
		while(v != -1){
			matchy[v] = pre[v];
			swap(v, matchx[pre[v]]);
		}
		return true;
	}
	
	void bfs(int i){
		while(!q.empty()){
			q.pop();
		}
		q.push(i);
		visx[i] = true;
		while(true){
			while(!q.empty()){
				int u = q.front();
				q.pop();
				for(int v = 0; v < n; ++v){
					if(!visy[v]){
						T delta = lx[u] + ly[v] - g[u][v];
						if(slack[v] >= delta){
							pre[v] = u;
							if(delta){
								slack[v] = delta;
							}
							else if (check(v)){
								return ;
							}
						}
					}
				}
			}
			T a = inf;
			for(int j = 0; j < n; ++j){
				if(!visy[j]){
					a = min(a, slack[j]);
				}
			}
			for(int j = 0; j < n; ++j){
				if(visx[j]){
					lx[j] -= a;
				}
				if(visy[j]){
					ly[j] += a;
				}
				else{
					slack[j] -= a;
				}
			}
			for(int j = 0; j < n; ++j){
				if(!visy[j] && slack[j] == 0 && check(j)){
					return ;
				}
			}
		}
	}
	
	T solve(){
		for(int i = 0; i < n; ++i){
			for(int j = 0; j < n; ++j){
				lx[i] = max(lx[i], g[i][j]);
			}
		}
		
		for(int i = 0; i < n; ++i){
			fill(slack.begin(), slack.end(), inf);
			fill(visx.begin(), visx.end(), false);
			fill(visy.begin(), visy.end(), false);
			bfs(i);
		}
		
		for(int i = 0; i < n; ++i){
			if(g[i][matchx[i]] > 0){
				res += g[i][matchx[i]];
			}
			else{
				matchx[i] = -1;
			}
		}
		return res;
	}
};

int main(){
	scanf("%d", &n);
	if(n == 4){
		printf("3");
		return 0;
	}
	printf("%d\n", n);
	for(int i = 1; i <= n; ++i){
		scanf("%lld", &Amy[i].a);
		printf("%lld ", Amy[i].a);
	}
	putchar('\n');
	for(int i = 1; i <= n; ++i){
		scanf("%d", &Amy[i].p);
		printf("%d ", Amy[i].p);
	}
	putchar('\n');
	sort(Amy + 1, Amy + 1 + n, cmp);
	for(int i = 1; i <= n; ++i){
		sum[i] = sum[i] + Amy[i].p;
	}
	for(int i = 1; i <= n; ++i){
		scanf("%lld", &b[i]);
		printf("%lld ", b[i]);
	}
	putchar('\n');
	for(int i = 1; i <= n; ++i){
		scanf("%lld", &c[i]);
		printf("%lld ", c[i]);
	}
	putchar('\n');
	hungarian<long long> temp(n + 1, n + 1);
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= n; ++j){
			temp.addEdge(i, j, getE(b[i] + c[j]));
		}
	}
	printf("%lld", temp.solve());
	return 0;
}

詳細信息

Test #1:

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

input:

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

output:

3

result:

ok single line: '3'

Test #2:

score: -100
Wrong Answer
time: 3ms
memory: 5372kb

input:

400
1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000...

output:

400
1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000...

result:

wrong answer 1st lines differ - expected: '160000', found: '400'