QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#609481#9412. Stop the CastleUESTC_DECAYALI#WA 1ms3812kbC++203.4kb2024-10-04 13:12:172024-10-04 13:12:19

Judging History

This is the latest submission verdict.

  • [2024-10-04 13:12:19]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3812kb
  • [2024-10-04 13:12:17]
  • Submitted

answer

#include<cstdio>
#include<iostream>
#include<map>
#include<utility>
#include<vector>
#include<cstring>
#include<algorithm>
#define RI register int
#define CI const int&
#define fi first
#define se second
using namespace std;
const int N=205;
int t,n,m,mat[N],vis[N],ok[N]; pair <int,int> c[N],o[N];
map <int,vector <int>> BR,BC; vector <int> v[N];
inline bool find(CI now,CI idx)
{
    for (auto to:v[now]) if (vis[to]!=idx)
    {
        vis[to]=idx;
        if (mat[to]==-1||find(mat[to],idx))
        return mat[to]=now,1;
    }
    return 0;
}
int main()
{
    // freopen("H.in","r",stdin);
    for (scanf("%d",&t);t;--t)
    {
        scanf("%d",&n); BR.clear(); BC.clear();
        for (RI i=1;i<=n;++i)
        scanf("%d%d",&c[i].fi,&c[i].se);
        scanf("%d",&m);
        for (RI i=1;i<=m;++i)
        {
            scanf("%d%d",&o[i].fi,&o[i].se);
            BR[o[i].fi].push_back(o[i].se);
            BC[o[i].se].push_back(o[i].fi);
        }
        for (auto& [_,it]:BR) sort(it.begin(),it.end());
        for (auto& [_,it]:BC) sort(it.begin(),it.end());
        vector <pair <int,int>> L,R; bool flag=1;
        for (RI i=1;i<=n;++i) for (RI j=i+1;j<=n;++j)
        {
            if (c[i].fi!=c[j].fi) continue;
            int l=c[i].se,r=c[j].se;
            if (l>r) swap(l,r);
            if (l+1==r) flag=0;
            auto& it=BR[c[i].fi];
            if (lower_bound(it.begin(),it.end(),l)!=lower_bound(it.begin(),it.end(),r)) continue;
            L.push_back({i,j});
        }
        for (RI i=1;i<=n;++i) for (RI j=i+1;j<=n;++j)
        {
            if (c[i].se!=c[j].se) continue;
            int l=c[i].fi,r=c[j].fi;
            if (l>r) swap(l,r);
            if (l+1==r) flag=0;
            auto& it=BC[c[i].se];
            if (lower_bound(it.begin(),it.end(),l)!=lower_bound(it.begin(),it.end(),r)) continue;
            R.push_back({i,j});
        }
        if (!flag) { puts("-1"); continue; }
        // for (auto [x,y]:L) printf("L:(%d,%d)\n",x,y);
        // for (auto [x,y]:R) printf("R:(%d,%d)\n",x,y);
        for (RI i=0;i<L.size();++i)
        for (RI j=0;j<R.size();++j)
        {
            int X=c[L[i].fi].fi,Y=c[R[j].fi].se;
            int xl=c[R[j].fi].fi,xr=c[R[j].se].fi;
            int yl=c[L[i].fi].se,yr=c[L[i].se].se;
            if (xl>xr) swap(xl,xr);
            if (yl>yr) swap(yl,yr);
            if (X<=xl||X>=xr||Y<=yl||Y>=yr) continue;
            v[i].push_back(j);
        }
        memset(vis,-1,sizeof(vis));
        memset(ok,-1,sizeof(ok));
        memset(mat,-1,sizeof(mat));
        for (RI i=0;i<L.size();++i) find(i,i);
        vector <pair <int,int>> ans;
        for (RI i=0;i<R.size();++i)
        if (mat[i]!=-1)
        {
            int u=mat[i],v=i; ok[u]=1;
            int X=c[L[u].fi].fi,Y=c[R[v].fi].se;
            ans.push_back({X,Y});
        }
        for (RI i=0;i<L.size();++i)
        if (ok[i]==-1)
        {
            auto [u,v]=L[i];
            int l=c[u].se,r=c[v].se;
            if (l>r) swap(l,r);
            ans.push_back({c[u].fi,l+1});
        }
        for (RI i=0;i<R.size();++i)
        if (mat[i]==-1)
        {
            auto [u,v]=R[i];
            int l=c[u].fi,r=c[v].fi;
            if (l>r) swap(l,r);
            ans.push_back({l+1,c[u].se});
        }
        printf("%d\n",(int)ans.size());
        for (auto [x,y]:ans) printf("%d %d\n",x,y);
    }
    return 0;
}

詳細信息

Test #1:

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

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

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

result:

wrong answer Duplicated position (16, 10) (test case 2)