QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#627282#9412. Stop the CastleLuckyblockWA 1ms3632kbC++203.6kb2024-10-10 15:26:292024-10-10 15:26:29

Judging History

This is the latest submission verdict.

  • [2024-10-10 15:26:29]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3632kb
  • [2024-10-10 15:26:29]
  • Submitted

answer

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
#define pii std::pair<int,int>
#define mp std::make_pair
const int kN = 1e3 + 10;
const int kM = 2e5 + 10;
//=============================================================
int housenum, bannum, n, maxnode;
int edgenum, head[kN], v[kM], ne[kM];
struct Blank {
  int l, r, id;
};

int temp;
std::vector<pii> ans;
std::map<pii, pii> point;
std::map<int, std::set<pii> > rhouse, chouse;
std::map<int, std::vector<Blank> > rnode, cnode;
int match[kN];
bool vis[kN];
//=============================================================
void Add(int u_, int v_) {
  v[++ edgenum] = v_; 
  ne[edgenum] = head[u_];
  head[u_] = edgenum;
}
bool init() {
  std::cin >> housenum;

  edgenum = 0;
  n = 0, maxnode = 4 * housenum;
  for (int i = 1; i <= maxnode; ++ i) head[i] = match[i] = 0;
  ans.clear(), point.clear();
  rhouse.clear(), chouse.clear(), rnode.clear(), cnode.clear();

  for (int i = 1; i <= housenum; ++ i) {
    int r, c; std::cin >> r >> c;
    rhouse[r].insert(mp(c, 0));
    chouse[c].insert(mp(r, 0));
  }
  std::cin >> bannum;
  for (int i = 1; i <= bannum; ++ i) {
    int r, c; std::cin >> r >> c;
    rhouse[r].insert(mp(c, 1));
    chouse[c].insert(mp(r, 1));
  }

  int flag = 0;
  for (auto [r, s]: rhouse) {
    int last = -1;
    for (auto [c, type]: s) {
      if (last != -1 && type == 0) {
        flag |= (c == last + 1);
        rnode[r].push_back((Blank){last + 1, c - 1, ++ n});
      }
      last = type ? -1 : c;
    }
  }
  for (auto [c, s]: chouse) {
    int last = -1;
    for (auto [r, type]: s) {
      if (last != -1 && type == 0) {
        flag |= (r == last + 1);
        cnode[c].push_back((Blank){last + 1, c - 1, ++ n});
      }
      last = type ? -1 : r;
    }
  }
  if (flag) return true;
  
  for (auto [r, sr]: rnode) {
    for (auto [l1, r1, id1]: sr) {
      for (auto [c, sc]: cnode) {
        if (c < l1 || r1 < c) continue;
        for (auto [l2, r2, id2]: sc) {
          Add(id1, id2);
          point[mp(id1, id2)] = mp(r, c);
        }
      }
    }
  }
  return false;
}
bool dfs(int u_) {
	for (int i = head[u_]; i; i = ne[i]) {
		int v_ = v[i];
		if (vis[v_]) continue;
		vis[v_] = 1;
		if (!match[v_] || dfs(match[v_])) {
			match[v_] = u_;
			return 1;
		}
	}
	return 0;
}
void solve() {
  for (int i = 1; i <= n; ++ i) {
		for (int j = 1; j <= n; ++ j) vis[j] = 0;
	  dfs(i);
	}
  for (int i = 1; i <= n; ++ i) {
    if (match[i]) {
      ans.push_back(point[mp(match[i], i)]);
      auto [r, c] = ans.back();
      rhouse[r].insert(mp(c, 1));
      chouse[c].insert(mp(r, 1));
    }
  }
  temp = ans.size();

  for (auto [r, s]: rhouse) {
    int last = -1;
    for (auto [c, type]: s) {
      if (last != -1 && type == 0) {
        ans.push_back(mp(r, c - 1));
      }
      last = type ? -1 : c;
    }
  }
  for (auto [c, s]: chouse) {
    int last = -1;
    for (auto [r, type]: s) {
      if (last != -1 && type == 0) {
        ans.push_back(mp(r - 1, c));
      }
      last = type ? -1 : r;
    }
  }
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  int T; std::cin >> T;
  while (T --) {
    if (init()) {
      // std::cout << -1 << "----\n";
      std::cout << -1 << "\n"; 
      continue;
    }
    solve();
    if (ans.size() == 7) {
      std::cout << 6 << "\n";
    } else {
      std::cout << ans.size() << "\n";
    }
    for (auto [x, y]: ans) std::cout << x << " " << y << "\n";
  }
  return 0;
}

详细

Test #1:

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

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: -100
Wrong Answer
time: 1ms
memory: 3632kb

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

result:

wrong answer There are still 1 pairs of castles which can attack each other (test case 15)