QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#461477#6880. Operation HopeFortitudeTL 0ms0kbC++233.6kb2024-07-02 19:25:292024-07-02 19:25:29

Judging History

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

  • [2024-07-02 19:25:29]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-07-02 19:25:29]
  • 提交

answer

#include <bits/stdc++.h>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define f first
#define s second
using namespace std;
using ll = long long;
using pii = pair <int, int>;
const int N = 1e5 + 5;
vector <int> g[14 * N];
int val[14 * N], comp[14 * N], tt;
int info[N * 12], cur, cnt;
inline void either(int f, int j) {
    f = max(2*f, -1-2*f);
    j = max(2*j, -1-2*j);
    g[f].push_back(j^1);
    g[j].push_back(f^1);
    if (tt) {
        info[cur++] = f;
        info[cur++] = j;
    }
}
inline void clr() {
    for (int i = 0; i < 2 * cnt; ++i) {
        g[i].clear();
    }
}
vector <int> z;
int tme = 0;
int dfs(int i) {
    int low = val[i] = ++tme, x; z.push_back(i);
    for(int e : g[i]) if (!comp[e])
        low = min(low, val[e] ?: dfs(e));
    if (low == val[i]) do {
        x = z.back(); z.pop_back();
        comp[x] = low;
    } while (x != i);
    return val[i] = low;
}
inline bool solvet() {
    for (int i = 0; i < 2 * cnt; ++i) 
        comp[i] = val[i] = 0;
    for (int i = 0; i < 2 * cnt; ++i) {
        if (!comp[i]) dfs(i);
    }
    for (int i = 0; i < cnt; ++i) {
        if (comp[2*i] == comp[2*i+1]) return 0;
    }
    return 1;
}
int nos[3][2 * N], ind[3][N], _ind[3][N];
int n, a[N][3], _a[N][3], d[N], _d[N];
vector <int> vals[3];
inline bool can(int x) {
	for (int j = 0; j < 3; ++j) {
		int r = -1, r2 = -1;
		for (int _i = 0; _i < n; ++_i) {
			int i = ind[j][_i];
			while (r + 1 < sz(vals[j]) && vals[j][r + 1] <= a[i][j] + x)
				++r;
			if (r + 1 < sz(vals[j])) {
				tt++;
				either(~d[i], nos[j][r + 1]);
			}
            i = _ind[j][_i];
			while (r2 + 1 < sz(vals[j]) && vals[j][r2 + 1] <= _a[i][j] + x)
				++r2;
			if (r2 + 1 < sz(vals[j])) {
				++tt;
				either(d[i], nos[j][r2 + 1]);
			}
		}
	}
	bool res = solvet();
	while (tt > 0) {
		g[info[--cur]].pop_back();
        g[info[--cur]].pop_back();
        tt--;
	}
	return res;
}
inline int solve() {
	cin >> n;
	//n = 10;
	for (int j = 0; j < 3; ++j)
		vals[j].clear();    
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < 3; ++j) {
			cin >> a[i][j];
			//a[i][j] = rand() % 1000 + 1;
			vals[j].pb(a[i][j]);
		}
		for (int j = 0; j < 3; ++j) {
			cin >> _a[i][j];
			//_a[i][j] = rand() % 1000 + 1;	
			vals[j].pb(_a[i][j]);
		}
	}
	for (int j = 0; j < 3; ++j) {
		sort(all(vals[j]));
		for (int i = 0; i < n; ++i)
			ind[j][i] = _ind[j][i] = i + 1;
		sort(ind[j], ind[j] + n, [&] (int x, int y) {
			return a[x][j] < a[y][j];
		});
		sort(_ind[j], _ind[j] + n, [&] (int x, int y) {
			return _a[x][j] < _a[y][j];
		});
	}
    clr();
    cnt = 0;
    for (int j = 0; j < 3; ++j) {
		for (int i = 0; i < sz(vals[j]); ++i)
			nos[j][i] = ++cnt;
	}
	for (int i = 1; i <= n; ++i) 
		d[i] = ++cnt;
    ++cnt;
	for (int j = 0; j < 3; ++j) {
		int v = 0;
		for (int _i = 0; _i < n; ++_i) {
			int i = ind[j][_i];
			while (v < sz(vals[j]) && vals[j][v] < a[i][j])
				++v;
			either(~d[i], ~nos[j][v]);
		}
		v = 0;
		for (int _i = 0; _i < n; ++_i) {
			int i = _ind[j][_i];
			while (v < sz(vals[j]) && vals[j][v] < _a[i][j])
				++v;
			either(d[i], ~nos[j][v]);
		}
	}
	for (int j = 0; j < 3; ++j) {
		for (int i = 0; i + 1 < sz(vals[j]); ++i)
			either(~nos[j][i], nos[j][i + 1]);
	}
	int l = 0, r = 1e9, ans = 1e9;
	while (r >= l) {
		int m = (l + r) / 2;
		if (can(m))
			ans = m, r = m - 1;
		else
			l = m + 1;
	}
	return ans;
}
int main() {
	ios :: sync_with_stdio(false);
	cin.tie(nullptr);
    int T;
	cin >> T;
	while (T--) {
		cout << solve() << '\n';
	}
	return 0;
}

詳細信息

Test #1:

score: 0
Time Limit Exceeded

input:

99
1000
532114032 55099632 197592060 601440117 964448551 693620489
68503446 149314803 308777541 408078601 977772348 978400861
185066959 236214410 460480442 842502015 709303988 675932475
793016330 161748857 511444978 852914351 281720292 552030608
9982160 15933748 8254470 175080600 567563770 461489051...

output:


result: