QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#604245#9412. Stop the Castleucup-team3474WA 1ms5636kbC++206.1kb2024-10-02 02:29:592024-10-02 02:30:00

Judging History

This is the latest submission verdict.

  • [2024-10-02 02:30:00]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 5636kb
  • [2024-10-02 02:29:59]
  • 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);
    int tc=0;
	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) {
                tc++;
				g.addedge(i + 1, row.size() + j + 1, 1);
			}
		}
	}

	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();
if(n>100) cout<<tc<<endl;
if(n<=100)
	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});
		}
	}
if(n<=100)
	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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 5636kb

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: 0ms
memory: 3632kb

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:

106
130

result:

wrong output format Unexpected end of file - int32 expected (test case 1)