QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#609821#9412. Stop the CastleUESTC_OldEastWest#WA 3ms14984kbC++178.1kb2024-10-04 14:09:012024-10-04 14:09:02

Judging History

This is the latest submission verdict.

  • [2024-10-04 14:09:02]
  • Judged
  • Verdict: WA
  • Time: 3ms
  • Memory: 14984kb
Show
  • [2024-10-04 14:09:01]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;

namespace Dinic {
	int n, s, t, tot;
	std::vector<int> to, nxt, cap, head;
	std::vector<int> cur, dep;

	void AddEdge(int u, int v, int c) {
		to[tot] = v, nxt[tot] = head[u], cap[tot] = c, head[u] = tot++;
	}

	void Init(int _n, int _s, int _t, std::vector<std::array<int, 3> > &edge) {
		n = _n, s = _s, t = _t, tot = 0;
		int m = edge.size();
		to = nxt = cap = std::vector<int>(m << 1);
		head = cur = dep = std::vector<int>(n, -1);
		for (auto [u, v, c] : edge) {
			AddEdge(u, v, c);
			AddEdge(v, u, 0);
		}
	}

	bool BFS() {
		dep = std::vector<int>(n, -1);
		std::vector<int> que(1, s);
		dep[s] = 0;
		for (int h = 0, u; h < que.size(); ++h) {
			u = que[h];
			for (int i = head[u], v, c; ~i; i = nxt[i]) {
				v = to[i], c = cap[i];
				if (dep[v] == -1 && c) dep[v] = dep[u] + 1, que.emplace_back(v);
			}
		}
		return dep[t] != -1;
	}

	int DFS (int u, int in) {
		if (u == t || !in) return in;
		int out = 0;
		for (int i = cur[u], v, c; ~i; i = nxt[i]) {
			cur[u] = nxt[i];
			v = to[i], c = cap[i];
			if (c && dep[v] == dep[u] + 1) {
				int ret = DFS(v, std::min(in, c));
				in -= ret, out += ret;
				cap[i] -= ret, cap[i ^ 1] += ret;
			}
		}
		return out;
	}

	int getMaxFlow() {
		int ans = 0;
		while (BFS()) {
			cur = head;
			ans += DFS(s, INT_MAX);
		}
		return ans;
	}
}


void charming() {
  int n; std::cin >> n;
  std::vector<std::pair<int, int> > castle;
  std::vector<int> all_r, all_c;
  for (int i = 0, r, c; i < n; ++i) {
    std::cin >> r >> c;
    castle.emplace_back(std::make_pair(r, c));
    all_r.emplace_back(r), all_r.emplace_back(r - 1), all_r.emplace_back(r + 1);
    all_c.emplace_back(c), all_c.emplace_back(c + 1), all_c.emplace_back(c - 1);
  }

  int m; std::cin >> m;
  std::vector<std::pair<int, int> > obstacle;
  for (int i = 0, r, c; i < m; ++i) {
    std::cin >> r >> c;
    all_r.emplace_back(r), all_r.emplace_back(r - 1), all_r.emplace_back(r + 1);
    all_c.emplace_back(c), all_c.emplace_back(c + 1), all_c.emplace_back(c - 1);
    obstacle.emplace_back(std::make_pair(r, c));
  }
  
  sort(all_r.begin(), all_r.end());
  all_r.resize(unique(all_r.begin(), all_r.end()) - all_r.begin());
  sort(all_c.begin(), all_c.end());
  all_c.resize(unique(all_c.begin(), all_c.end()) - all_c.begin());

  for (int i = 0; i < n; ++i) {
    int r = castle[i].first, c = castle[i].second;
    r = lower_bound(all_r.begin(), all_r.end(), r) - all_r.begin() + 1;
    c = lower_bound(all_c.begin(), all_c.end(), c) - all_c.begin() + 1;
    castle[i] = std::make_pair(r, c);
  }

  for (int i = 0; i < m; ++i) {
    int r = obstacle[i].first, c = obstacle[i].second;
    r = lower_bound(all_r.begin(), all_r.end(), r) - all_r.begin() + 1;
    c = lower_bound(all_c.begin(), all_c.end(), c) - all_c.begin() + 1;
    obstacle[i] = std::make_pair(r, c);
  }

  std::function<bool(int, int, int)> Check = [&](int x, int y, int z) {
    if (x > y) std::swap(x, y);
    if (z > x && z < y) return true;
    else return false;
  };

  std::function<bool(int, int, int, int)> hinder = [&](int idx0, int idx1, int idx2, int type) {
    bool r_same = castle[idx0].first == castle[idx1].first;
    if (type == 0) {
      if (r_same) {
      	if (castle[idx2].first != castle[idx0].first) return false;
        int c0 = castle[idx0].second, c1 = castle[idx1].second, c2 = castle[idx2].second;
        return Check(c0, c1, c2);
      }
      else {
      	if (castle[idx2].second != castle[idx0].second) return false;
        int r0 = castle[idx0].first, r1 = castle[idx1].first, r2 = castle[idx2].first;
        return Check(r0, r1, r2);
      }
    }
    else {
      if (r_same) {
      	if (obstacle[idx2].first != castle[idx0].first) return false;
        int c0 = castle[idx0].second, c1 = castle[idx1].second, c2 = obstacle[idx2].second;
        return Check(c0, c1, c2);
      }
      else {
      	if (obstacle[idx2].second != castle[idx0].second) return false;
        int r0 = castle[idx0].first, r1 = castle[idx1].first, r2 = obstacle[idx2].first;
        return Check(r0, r1, r2);
      }
    }
  };

  int s = 0, t = 1, tot = 2;
  std::map<int, int> mp0;
  std::map<std::pair<int, int>, int> mp1;
  std::vector<std::array<int, 3> > edge;
  bool chk = true;
  int max_r = int(all_r.size()) + 1;
  int max_c = int(all_c.size()) + 1;

  int ans = 0, c = 0;
  std::vector<std::vector<int> > set;
  std::vector vec(max_r, std::vector (max_c, std::vector<int> ()));
  std::vector<std::pair<int, int> > pos;
  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      if (abs(castle[i].first - castle[j].first) + abs(castle[i].second - castle[j].second) <= 1) {
        chk = false;
        break;
      }
      if (castle[i].first == castle[j].first || castle[i].second == castle[j].second) {
        bool fight = true;
        for (int k = 0; k < n; ++k) if (k != i && k != j) {
          if (hinder(i, j, k, 0)) {fight = false; break;}
        }
        for (int k = 0; k < m && fight; ++k) {
          if (hinder(i, j, k, 1)) {fight = false; break;}
        }
        if (fight) {
          ++ans, ++c;
          set.emplace_back(std::vector<int> (1, c));
          if (castle[i].first == castle[j].first) {
          	pos.emplace_back(std::make_pair(castle[i].first, std::min(castle[i].second, castle[j].second) + 1));
            int l = castle[i].second, r = castle[j].second;
            if (l > r) std::swap(l, r);
            for (int k = l + 1; k < r; ++k) {
              vec[castle[i].first][k].emplace_back(c);
            }
          }
          else {
          	pos.emplace_back(std::make_pair(std::min(castle[i].first, castle[j].first) + 1, castle[i].second));
            int l = castle[i].first, r = castle[j].first;
            if (l > r) std::swap(l, r);
            for (int k = l + 1; k < r; ++k) {
              vec[k][castle[i].second].emplace_back(c);
            }
          }
        }
      }
    }
    if (!chk) break;
  }

  if (!chk) {
    std::cout << -1 << '\n';
    return;
  }

//	std::vector<std::pair<int, int> > two_set;
//	std::vector<std::vector<int> > conf(c + 1);
//	
//	int two_cnt = 0;
  for (int i = 1; i < max_r; ++i) {
    for (int j = 1; j < max_c; ++j) {
      if (vec[i][j].size() > 1) {
      	pos.emplace_back(std::make_pair(i, j));
        set.emplace_back(vec[i][j]);
//        two_set.emplace_back(i);
//        for (int x : vec[i][j]) conf[x].emplace_back(i);
//        mp0[i] = tot++;
//        ++two_cnt;
//        edge.emplace_back((std::array<int, 3>) {s, tot - 1, 1});
      }
    }
  }
//  for (int i = 0; i < c; ++i) {
//  	int siz = conf[i].size();
//		for (int j = 0; j < siz; ++j) {
//		
//		}
//  }
  

	reverse(pos.begin(), pos.end());
  reverse(set.begin(), set.end());
  int set_cnt = set.size();
  std::vector<int> used(N), vis(N);
  std::vector<std::pair<int, int> > ans_pos;
  while (true) {
    bool brk = true;
    for (int i = 0; i < set_cnt; ++i) if (!used[i]) {
      if (int(set[i].size()) < 2) break;
      bool two = true;
      for (int x : set[i]) {
        if (vis[x]) {two = false; break;}
      }
      if (two) {
        for (int x : set[i]) vis[x] = 1;
        ans_pos.emplace_back(pos[i]);
        --ans;
        brk = false;
        break;
      }
    }
    if (brk) break;
  }
  for (int i = 0; i < set_cnt; ++i) if (!used[i]) {
  	bool ok = false;
		for (int x : set[i]) {
			if (!vis[x]) {
				vis[x] = 1;
				ok = true;
			}
		}
		if (ok) {
			ans_pos.emplace_back(pos[i]);
		}
  }

  std::cout << ans << '\n';
  for (auto [r, c] : ans_pos) {
  	std::cout << all_r[r - 1] << ' ' << all_c[c - 1] << '\n';
  }
  

  // int set_cnt = set.size();
  // for (int i = 0; i < set_cnt; ++i) {
  //   mp0[i] = tot++;
  //   for (int x : set[i]) {
  //     edge.emplace_back();
  //   } 
  // }

}

signed main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(NULL);
  std::cout.tie(NULL);
  int t; std::cin >> t;
  while (t--) charming();
  return 0;
}
源文件, 语言: C++17

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 11148kb

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
4 6
2 3
0
1
2 3
-1

result:

ok ok 4 cases (4 test cases)

Test #2:

score: 0
Accepted
time: 0ms
memory: 14984kb

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

result:

ok ok 21 cases (21 test cases)

Test #3:

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

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:

51
393 307
352 305
349 138
334 367
311 374
277 356
270 275
224 153
199 467
185 160
154 496
132 67
126 61
94 35
52 139
393 186
393 112
352 61
311 177
311 147
306 374
260 275
199 432
187 467
154 305
126 275
91 160
453 251
440 179
415 305
390 308
380 385
311 455
286 367
278 272
277 189
274 67
271 186
2...

result:

wrong answer Participant's answer is 51, but jury has better answer 46 (test case 1)
English 繁體中文 简体中文

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