QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#604204#9412. Stop the Castleucup-team3474WA 1ms5900kbC++206.7kb2024-10-02 01:29:242024-10-02 01:29:25

Judging History

This is the latest submission verdict.

  • [2024-10-02 01:29:25]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 5900kb
Show
  • [2024-10-02 01:29:24]
  • Submitted

answer

/*
 
_/      _/    _/      _/    _/      _/   _/_/_/_/_/     _/_/       _/      _/ 
 _/    _/     _/      _/     _/    _/        _/       _/    _/     _/      _/            
  _/  _/      _/      _/      _/  _/         _/      _/      _/    _/_/  _/_/         
   _/_/       _/_/_/_/_/        _/           _/      _/      _/    _/  _/  _/          
  _/  _/      _/      _/        _/           _/      _/      _/    _/      _/          
 _/    _/     _/      _/        _/           _/       _/    _/     _/      _/          
_/      _/    _/      _/        _/           _/         _/_/       _/      _/       
 
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
using i64 = long long;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)
#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define multi int _;cin>>_;while(_--)
#define debug(x) cerr << #x << " = " << (x) << endl;
#define int long long
#define pb push_back
#define eb emplace_back
ll gcd(ll a,ll b){ return b?gcd(b,a%b):a;}
mt19937_64 mrand(chrono::steady_clock().now().time_since_epoch().count());
int rnd(int l,int r){ return mrand() % (r - l + 1) + l;}
void test() {cerr << "\n";}
template<typename T, typename... Args> 
void test(T x, Args... args) {cerr << x << " ";test(args...);}
const ll MOD = 998244353;
// const ll MOD = 1e9+7;
ll ksm(ll x,ll y){ll ans=1;x%=MOD;while(y){if(y&1)ans=ans*x%MOD;x=x*x%MOD,y/=2;}return ans;}

const int P1 = 972152273, base1 = 809;
const int P2 = 905563261, base2 = 919;
const ll N = 200005;
//head

using ll = long long;

const int V = 1010;
const int E = 101000;
template<typename T>
struct MaxFlow
{
    int s, t, vtot;
    int head[V], etot;
    int dis[V], cur[V];
    struct edge
    {
        int v, nxt;
        T f;
    }e[E * 2];
    void addedge(int u, int v, T f)
    {
        e[etot] = {v, head[u], f}; head[u] = etot++;
        e[etot] = {u, head[v], 0}; head[v] = etot++;
    }
    bool bfs()
    {
        for(int i = 1 ; i <= vtot ; i++ )
        {
            dis[i] = 0;
            cur[i] = head[i];
        }
        queue<int> q;
        q.push(s); dis[s] = 1;
        while(!q.empty())
        {
            int u = q.front(); q.pop();
            for(int i = head[u] ; ~i ; i = e[i].nxt)
            {
                if(e[i].f && !dis[e[i].v])
                {
                    int v = e[i].v;
                    dis[v] = dis[u] + 1;
                    if(v == t) return true;
                    q.push(v);
                }
            }
        }
        return false;
    }
    T dfs(int u, T m)
    {
        if(u == t) return m;
        T flow = 0;
        for(int i = cur[u]; ~i ; cur[u] = i = e[i].nxt)
        {
            if(e[i].f && dis[e[i].v] == dis[u] + 1)
            {
                T f = dfs(e[i].v, min(m, e[i].f));
                e[i].f -= f;
                e[i ^ 1].f += f;
                m -= f;
                flow += f;
                if(!m) break;
            }
        }
        if(!flow) dis[u] = -1;
        return flow;
    }
    T dinic()
    {
        T flow = 0;
        while(bfs()) flow += dfs(s, numeric_limits<T>::max());
        return flow;
    }
    void init(int s_, int t_, int vtot_ )
    {
        s = s_;
        t = t_;
        vtot = vtot_;
        etot = 0;
        for(int i = 1 ; i <= vtot ; i++ )
        {
            head[i] = -1;
        }
    } 
};

MaxFlow<ll> g;

void solve(int testcase) {
	int n;
	std::cin >> n;
	std::vector<std::pair<int, int>> a(n + 1);
	for (int i = 1; i <= n; i++) {
		int x, y;
		std::cin >> x >> y;
		a[i] = {x, y};
	}

	std::sort(a.begin() + 1, a.end());

	int m;
	std::cin >> m;
	std::vector<std::pair<int, int>> b(m + 1);
	for (int i = 1; i <= m; i++) {
		int x, y;
		std::cin >> x >> y;
		b[i] = {x, y};
	}
	std::vector<std::array<int, 4>> row, column;
	for (int i = 2; i <= n; i++) {
		if (a[i - 1].first == a[i].first) {
			if (a[i - 1].second + 1 == a[i].second) {
				std::cout << "-1\n";
				return;
			}
			for (int j = 1; j <= m; j++) {
				auto [x1, y1] = a[i - 1];
				auto [x2, y2] = a[i];
				auto [x3, y3] = b[j];
				if (x3 == x1 && y1 < y3 && y3 < y2) {
					goto OK1;
				}
			}
			row.push_back({a[i - 1].first, a[i - 1].second, a[i].first, a[i].second});
			OK1:;
		}
	}

	std::sort(a.begin() + 1, a.end(), [&](const auto &a, const auto &b) {
		if (a.second == b.second) return a.first < b.first;
		return a.second < b.second;
	});
	for (int i = 2; i <= n; i++) {
		if (a[i - 1].second == a[i].second) {
			if (a[i - 1].first + 1 == a[i].first) {
				std::cout << "-1\n";
				return;
			}
			for (int j = 1; j <= m; j++) {
				auto [x1, y1] = a[i - 1];
				auto [x2, y2] = a[i];
				auto [x3, y3] = b[j];
				if (y1 == y3 && x1 < x3 && x3 < x2) {
					goto OK2;
				}
			}
			column.push_back({a[i - 1].first, a[i - 1].second, a[i].first, a[i].second});
			OK2:;
		}
	}

	int s = row.size() + column.size() + 1;
	int t = s + 1;
	g.init(s, t, t);
	for (int i = 0; i < row.size(); i++) {
		for (int j = 0; j < column.size(); j++) {
			auto [x1, y1, x2, y2] = row[i];
			auto [x3, y3, x4, y4] = column[j];
			if (x3 < x1 && x1 < x4 && y1 < y3 && y3 < y2) {
				g.addedge(i + 1, row.size() + j + 1, 1);
if(n>100) cout<<i+1<<" "<<j+1<<endl;
			}
		}
	}
if(n>100) exit(0);
	for (int i = 1; i <= row.size(); i++) {
		g.addedge(s, i, 1);
	}

	for (int i = 1; i <= column.size(); i++) {
		g.addedge(row.size() + i, t, 1);
	}

	std::vector<std::pair<int, int>> res;

	int ans = g.dinic();
	std::cout << row.size() + column.size() - ans << "\n";

	std::vector<int> vis1(row.size()), vis2(column.size());
	for (int i = 0; i < g.etot; i += 2) {
		int u = g.e[i ^ 1].v;
		int v = g.e[i].v;
		if (u >= s || v >= s) continue;
		if (g.e[i].f == 0) {
			vis1[u - 1] = 1;
			vis2[v - 1 - row.size()] = 1;
			auto [x1, y1, x2, y2] = row[u - 1];
			auto [x3, y3, x4, y4] = column[v - 1 - row.size()];
			res.push_back({x1, y3});
		}
	}

	for (int i = 0; i < row.size(); i++) {
		if (vis1[i] == 0) {
			auto [x1, y1, x2, y2] = row[i];
			res.push_back({x1, y1 + 1});
		}
	}

	for (int i = 0; i < column.size(); i++) {
		if (vis2[i] == 0) {
			auto [x1, y1, x2, y2] = column[i];
			res.push_back({x1 + 1, y1});
		}
	}

	for (auto [x, y] : res) {
		std::cout << x << " " << y << "\n";
	}
}

signed main()
{  
#ifdef localfreopen
    // freopen("1.in","r",stdin);
#endif
    fastio
    std::cout << std::fixed << std::setprecision(10);
    int t;
    cin >> t;
    for(int i = 1 ; i <= t ; i++ )
    {
        solve(i);
    }
    return 0;
}
源文件, 语言: C++20

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3660kb

input:

4
7
1 3
6 6
4 7
2 1
6 3
4 1
2 6
3
3 4
6 4
3 1
2
1 1
2 2
0
3
1 1
1 3
3 3
1
1 2
3
1 1
1 3
2 3
0

output:

2
2 3
4 6
0
1
2 3
-1

result:

ok ok 4 cases (4 test cases)

Test #2:

score: 0
Accepted
time: 1ms
memory: 5900kb

input:

21
11
3 5
18 6
19 12
27 48
28 38
30 12
33 18
42 18
43 38
45 46
48 34
3
2 6
24 4
41 45
15
11 6
15 27
16 9
16 14
16 48
19 26
25 12
27 26
28 4
31 40
32 6
33 50
37 50
46 11
50 29
17
1 49
4 9
9 15
9 22
11 31
11 46
14 28
17 5
17 49
18 43
20 31
30 46
33 11
33 33
34 15
36 6
47 10
2
16 46
36 30
11
7 34
7 41
...

output:

3
20 12
34 18
29 38
5
16 10
16 15
12 6
20 26
34 50
0
1
16 10
0
1
43 22
5
1 3
1 13
33 10
44 45
42 44
0
5
27 41
29 26
44 4
8 1
21 15
1
32 9
0
0
0
0
6
23 10
35 34
12 11
23 44
29 21
24 46
0
3
20 30
43 25
31 17
0
-1
3
16 36
25 7
17 39
6
7 5
8 11
5 5
6 4
4 9
3 10

result:

ok ok 21 cases (21 test cases)

Test #3:

score: -100
Wrong Answer
time: 1ms
memory: 3608kb

input:

2
200
7 52
9 160
10 4
12 61
18 436
19 430
20 499
24 139
25 416
29 53
33 153
35 275
35 310
37 25
38 477
39 349
42 120
44 158
45 330
49 486
50 204
51 67
52 138
52 305
56 139
63 132
66 4
67 327
70 484
71 67
72 308
74 218
76 479
81 139
82 90
86 201
87 335
91 35
91 220
92 496
94 29
94 436
96 359
97 299
1...

output:

2 11
2 14
2 15
2 20
3 5
3 8
3 10
3 14
3 15
4 3
4 5
4 8
4 10
4 14
4 15
4 20
4 21
5 5
5 8
5 10
5 14
5 15
6 20
7 3
7 5
7 8
7 10
7 14
7 15
7 20
7 21
8 10
8 14
8 15
8 20
8 21
9 27
9 32
9 34
10 3
10 5
10 8
10 10
10 13
10 14
10 15
12 32
13 10
13 13
13 14
13 15
13 20
13 21
13 24
13 27
13 30
13 32
14 3
14 5
...

result:

wrong answer There are still 66 pairs of castles which can attack each other (test case 1)
English 繁體中文 简体中文

服务器时间: 2025-02-08 21:04:05 | 开源项目