QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#169986#7178. Bishopsucup-team198#AC ✓275ms61732kbC++202.1kb2023-09-09 14:23:522023-09-09 14:31:06

Judging History

你现在查看的是最新测评结果

  • [2023-09-09 14:31:06]
  • 评测
  • 测评结果:AC
  • 用时:275ms
  • 内存:61732kb
  • [2023-09-09 14:23:52]
  • 提交

answer

#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
#include<map>
#include<cassert>
using namespace std;
// #define debug(x) cout<<"[debug]"#x<<"="<<x<<endl
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const ld eps=1e-8;
const int INF=0x3f3f3f3f,mod=998244353;
const ll INFF=0x3f3f3f3f3f3f3f3f;

#ifndef ONLINE_JUDGE
#define debug(...)
#include<debug>
#else
#define debug(...)
#endif

const int N=600005;
vector<int> g[N];
int bel[N];
int len;
vector<int> block[2];
bool dfs(int u, int color=1)
{
    if(bel[u])
        return bel[u]=color;
    bel[u]=color;
    block[color-1].push_back(u);
    for(int v:g[u])
        if(!dfs(v, 3-color))
            return false;
    return true;
}
vector<int> choose;
bool paint() {// 二分图染色
    for(int i=0; i<len; ++i) {
        if(bel[i]) continue;
        block[0].clear();
        block[1].clear();
        if(!dfs(i)) return false;
        if(block[0].size()>block[1].size()) {
            choose.insert(choose.end(),block[0].begin(),block[0].end());
        }else {
            choose.insert(choose.end(),block[1].begin(),block[1].end());
        }
    }
    return true;
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);

    vector<pii> all;
    for(int j=1;j<=m;j++) all.push_back({1,j});
    for(int i=2;i<=n;i++) all.push_back({i,m});
    for(int j=m-1;j>=1;j--) all.push_back({n,j});
    for(int i=n-1;i>=2;i--) all.push_back({i,1});

    map<int,int> dig;//对角线
    map<int,int> rdig;//反对角线

    auto add=[&](int x,int y){
        g[x].push_back(y);
        g[y].push_back(x);
    };
    for(int i=0;i<all.size();i++)
    {
        auto [x,y]=all[i];
        if(dig.count(x-y))
        {
            add(dig[x-y],i);
        }
        if(rdig.count(x+y))
        {
            add(rdig[x+y],i);
        }
        dig[x-y]=i;
        rdig[x+y]=i;
    }
    len=all.size();
    assert(paint());
    
    // choose 
    printf("%d\n",choose.size());
    for(auto i:choose)
    {
        auto [x,y]=all[i];
        printf("%d %d\n",x,y);
    }
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

score: 100
Accepted
time: 7ms
memory: 19840kb

input:

2 5

output:

6
1 1
1 3
1 5
2 3
2 5
2 1

result:

ok n: 2, m: 5, bishops: 6

Test #2:

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

input:

5 5

output:

8
5 5
4 5
2 1
3 5
3 1
2 5
4 1
5 1

result:

ok n: 5, m: 5, bishops: 8

Test #3:

score: 0
Accepted
time: 243ms
memory: 56688kb

input:

100000 100000

output:

199998
100000 100000
99999 100000
2 1
99998 100000
3 1
99997 100000
4 1
99996 100000
5 1
99995 100000
6 1
99994 100000
7 1
99993 100000
8 1
99992 100000
9 1
99991 100000
10 1
99990 100000
11 1
99989 100000
12 1
99988 100000
13 1
99987 100000
14 1
99986 100000
15 1
99985 100000
16 1
99984 100000
17 1...

result:

ok n: 100000, m: 100000, bishops: 199998

Test #4:

score: 0
Accepted
time: 245ms
memory: 61732kb

input:

100000 99999

output:

199998
1 1
100000 99998
1 3
100000 99996
1 5
100000 99994
1 7
100000 99992
1 9
100000 99990
1 11
100000 99988
1 13
100000 99986
1 15
100000 99984
1 17
100000 99982
1 19
100000 99980
1 21
100000 99978
1 23
100000 99976
1 25
100000 99974
1 27
100000 99972
1 29
100000 99970
1 31
100000 99968
1 33
10000...

result:

ok n: 100000, m: 99999, bishops: 199998

Test #5:

score: 0
Accepted
time: 183ms
memory: 53228kb

input:

100000 50000

output:

149998
50000 50000
100000 2
3 1
49998 50000
100000 4
5 1
49996 50000
100000 6
7 1
49994 50000
100000 8
9 1
49992 50000
100000 10
11 1
49990 50000
100000 12
13 1
49988 50000
100000 14
15 1
49986 50000
100000 16
17 1
49984 50000
100000 18
19 1
49982 50000
100000 20
21 1
49980 50000
100000 22
23 1
4997...

result:

ok n: 100000, m: 50000, bishops: 149998

Test #6:

score: 0
Accepted
time: 115ms
memory: 37760kb

input:

1 100000

output:

100000
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
1 ...

result:

ok n: 1, m: 100000, bishops: 100000

Test #7:

score: 0
Accepted
time: 239ms
memory: 49172kb

input:

34535 99889

output:

134423
1 1
1 69069
34535 96175
34535 27107
1 7429
1 76497
34535 88747
34535 19679
1 14857
1 83925
34535 81319
34535 12251
1 22285
1 91353
34535 73891
34535 4823
1 29713
1 98781
34535 66463
31929 1
1 37141
6321 99889
34535 59035
24501 1
1 44569
13749 99889
34535 51607
17073 1
1 51997
21177 99889
3453...

result:

ok n: 34535, m: 99889, bishops: 134423

Test #8:

score: 0
Accepted
time: 192ms
memory: 41688kb

input:

12231 97889

output:

110119
1 1
1 24461
1 48921
1 73381
1 97841
12231 85707
12231 61247
12231 36787
12231 12327
97 1
1 24365
1 48825
1 73285
1 97745
12231 85803
12231 61343
12231 36883
12231 12423
193 1
1 24269
1 48729
1 73189
1 97649
12231 85899
12231 61439
12231 36979
12231 12519
289 1
1 24173
1 48633
1 73093
1 97553
...

result:

ok n: 12231, m: 97889, bishops: 110119

Test #9:

score: 0
Accepted
time: 179ms
memory: 39820kb

input:

10000 100000

output:

109998
10000 10000
10000 29998
10000 49996
10000 69994
10000 89992
10 100000
1 80011
1 60013
1 40015
1 20017
1 19
10000 9982
10000 29980
10000 49978
10000 69976
10000 89974
28 100000
1 80029
1 60031
1 40033
1 20035
1 37
10000 9964
10000 29962
10000 49960
10000 69958
10000 89956
46 100000
1 80047
1 6...

result:

ok n: 10000, m: 100000, bishops: 109998

Test #10:

score: 0
Accepted
time: 151ms
memory: 39824kb

input:

13 99999

output:

100011
1 1
1 25
1 49
1 73
1 97
1 121
1 145
1 169
1 193
1 217
1 241
1 265
1 289
1 313
1 337
1 361
1 385
1 409
1 433
1 457
1 481
1 505
1 529
1 553
1 577
1 601
1 625
1 649
1 673
1 697
1 721
1 745
1 769
1 793
1 817
1 841
1 865
1 889
1 913
1 937
1 961
1 985
1 1009
1 1033
1 1057
1 1081
1 1105
1 1129
1 115...

result:

ok n: 13, m: 99999, bishops: 100011

Test #11:

score: 0
Accepted
time: 144ms
memory: 40864kb

input:

21 99999

output:

100019
1 1
1 41
1 81
1 121
1 161
1 201
1 241
1 281
1 321
1 361
1 401
1 441
1 481
1 521
1 561
1 601
1 641
1 681
1 721
1 761
1 801
1 841
1 881
1 921
1 961
1 1001
1 1041
1 1081
1 1121
1 1161
1 1201
1 1241
1 1281
1 1321
1 1361
1 1401
1 1441
1 1481
1 1521
1 1561
1 1601
1 1641
1 1681
1 1721
1 1761
1 1801
...

result:

ok n: 21, m: 99999, bishops: 100019

Test #12:

score: 0
Accepted
time: 208ms
memory: 49704kb

input:

49999 100000

output:

149998
1 1
1 99997
49999 50005
7 1
1 99991
49999 50011
13 1
1 99985
49999 50017
19 1
1 99979
49999 50023
25 1
1 99973
49999 50029
31 1
1 99967
49999 50035
37 1
1 99961
49999 50041
43 1
1 99955
49999 50047
49 1
1 99949
49999 50053
55 1
1 99943
49999 50059
61 1
1 99937
49999 50065
67 1
1 99931
49999 5...

result:

ok n: 49999, m: 100000, bishops: 149998

Test #13:

score: 0
Accepted
time: 152ms
memory: 50172kb

input:

33333 99999

output:

133331
1 1
1 66665
33331 99999
33333 33337
5 1
1 66661
33327 99999
33333 33341
9 1
1 66657
33323 99999
33333 33345
13 1
1 66653
33319 99999
33333 33349
17 1
1 66649
33315 99999
33333 33353
21 1
1 66645
33311 99999
33333 33357
25 1
1 66641
33307 99999
33333 33361
29 1
1 66637
33303 99999
33333 33365
...

result:

ok n: 33333, m: 99999, bishops: 133331

Test #14:

score: 0
Accepted
time: 189ms
memory: 45032kb

input:

23342 98876

output:

122216
23342 23342
23342 70024
5512 98876
1 57705
1 11023
23342 12320
23342 59002
16534 98876
1 68727
1 22045
23342 1298
23342 47980
23342 94662
1 79749
1 33067
13617 1
23342 36958
23342 83640
1 90771
1 44089
2595 1
23342 25936
23342 72618
2918 98876
1 55111
1 8429
23342 14914
23342 61596
13940 9887...

result:

ok n: 23342, m: 98876, bishops: 122216

Test #15:

score: 0
Accepted
time: 243ms
memory: 49968kb

input:

56713 91234

output:

147946
1 1
22192 91234
56713 12331
1 44383
56713 81373
24661 1
1 88765
56713 36991
1 19723
41914 91234
49321 1
1 64105
56713 61651
4939 1
17254 91234
56713 17269
1 39445
56713 86311
29599 1
1 83827
56713 41929
1 14785
36976 91234
54259 1
1 59167
56713 66589
9877 1
12316 91234
56713 22207
1 34507
566...

result:

ok n: 56713, m: 91234, bishops: 147946

Test #16:

score: 0
Accepted
time: 236ms
memory: 55920kb

input:

99995 99995

output:

199988
99995 99995
99994 99995
2 1
99993 99995
3 1
99992 99995
4 1
99991 99995
5 1
99990 99995
6 1
99989 99995
7 1
99988 99995
8 1
99987 99995
9 1
99986 99995
10 1
99985 99995
11 1
99984 99995
12 1
99983 99995
13 1
99982 99995
14 1
99981 99995
15 1
99980 99995
16 1
99979 99995
17 1
99978 99995
18 1
...

result:

ok n: 99995, m: 99995, bishops: 199988

Test #17:

score: 0
Accepted
time: 89ms
memory: 32192kb

input:

12345 54321

output:

66665
1 1
1 24689
1 49377
12345 46921
12345 22233
9889 1
1 14801
1 39489
9857 54321
12345 32121
12345 7433
1 4913
1 29601
1 54289
12345 42009
12345 17321
4977 1
1 19713
1 44401
12345 51897
12345 27209
12345 2521
1 9825
1 34513
4881 54321
12345 37097
12345 12409
65 1
1 24625
1 49313
12345 46985
12345...

result:

ok n: 12345, m: 54321, bishops: 66665

Test #18:

score: 0
Accepted
time: 275ms
memory: 58576kb

input:

90000 92000

output:

181998
90000 90000
1 4001
90000 86000
1 8001
90000 82000
1 12001
90000 78000
1 16001
90000 74000
1 20001
90000 70000
1 24001
90000 66000
1 28001
90000 62000
1 32001
90000 58000
1 36001
90000 54000
1 40001
90000 50000
1 44001
90000 46000
1 48001
90000 42000
1 52001
90000 38000
1 56001
90000 34000
1 6...

result:

ok n: 90000, m: 92000, bishops: 181998

Test #19:

score: 0
Accepted
time: 98ms
memory: 34836kb

input:

10000 70000

output:

79998
10000 10000
10000 29998
10000 49996
10000 69994
1 60007
1 40009
1 20011
1 13
10000 9988
10000 29986
10000 49984
10000 69982
1 60019
1 40021
1 20023
1 25
10000 9976
10000 29974
10000 49972
10000 69970
1 60031
1 40033
1 20035
1 37
10000 9964
10000 29962
10000 49960
10000 69958
1 60043
1 40045
1 ...

result:

ok n: 10000, m: 70000, bishops: 79998

Test #20:

score: 0
Accepted
time: 118ms
memory: 36536kb

input:

10000 70001

output:

80000
1 1
1 19999
1 39997
1 59995
9993 70001
10000 50010
10000 30012
10000 10014
15 1
1 19985
1 39983
1 59981
9979 70001
10000 50024
10000 30026
10000 10028
29 1
1 19971
1 39969
1 59967
9965 70001
10000 50038
10000 30040
10000 10042
43 1
1 19957
1 39955
1 59953
9951 70001
10000 50052
10000 30054
100...

result:

ok n: 10000, m: 70001, bishops: 80000

Test #21:

score: 0
Accepted
time: 143ms
memory: 37324kb

input:

10000 80000

output:

89998
10000 10000
10000 29998
10000 49996
10000 69994
8 80000
1 60009
1 40011
1 20013
1 15
10000 9986
10000 29984
10000 49982
10000 69980
22 80000
1 60023
1 40025
1 20027
1 29
10000 9972
10000 29970
10000 49968
10000 69966
36 80000
1 60037
1 40039
1 20041
1 43
10000 9958
10000 29956
10000 49954
1000...

result:

ok n: 10000, m: 80000, bishops: 89998

Test #22:

score: 0
Accepted
time: 142ms
memory: 38500kb

input:

10000 80001

output:

90000
1 1
1 19999
1 39997
1 59995
1 79993
10000 70010
10000 50012
10000 30014
10000 10016
17 1
1 19983
1 39981
1 59979
1 79977
10000 70026
10000 50028
10000 30030
10000 10032
33 1
1 19967
1 39965
1 59963
1 79961
10000 70042
10000 50044
10000 30046
10000 10048
49 1
1 19951
1 39949
1 59947
1 79945
100...

result:

ok n: 10000, m: 80001, bishops: 90000

Test #23:

score: 0
Accepted
time: 133ms
memory: 36512kb

input:

10000 80002

output:

90000
10000 10000
10000 29998
10000 49996
10000 69994
10 80002
1 60013
1 40015
1 20017
1 19
10000 9982
10000 29980
10000 49978
10000 69976
28 80002
1 60031
1 40033
1 20035
1 37
10000 9964
10000 29962
10000 49960
10000 69958
46 80002
1 60049
1 40051
1 20053
1 55
10000 9946
10000 29944
10000 49942
100...

result:

ok n: 10000, m: 80002, bishops: 90000

Test #24:

score: 0
Accepted
time: 121ms
memory: 36868kb

input:

10000 79999

output:

89998
1 1
1 19999
1 39997
1 59995
1 79993
10000 70006
10000 50008
10000 30010
10000 10012
13 1
1 19987
1 39985
1 59983
1 79981
10000 70018
10000 50020
10000 30022
10000 10024
25 1
1 19975
1 39973
1 59971
1 79969
10000 70030
10000 50032
10000 30034
10000 10036
37 1
1 19963
1 39961
1 59959
1 79957
100...

result:

ok n: 10000, m: 79999, bishops: 89998

Test #25:

score: 0
Accepted
time: 128ms
memory: 38932kb

input:

10000 79998

output:

89996
10000 10000
10000 29998
10000 49996
10000 69994
6 79998
1 60005
1 40007
1 20009
1 11
10000 9990
10000 29988
10000 49986
10000 69984
16 79998
1 60015
1 40017
1 20019
1 21
10000 9980
10000 29978
10000 49976
10000 69974
26 79998
1 60025
1 40027
1 20029
1 31
10000 9970
10000 29968
10000 49966
1000...

result:

ok n: 10000, m: 79998, bishops: 89996

Test #26:

score: 0
Accepted
time: 184ms
memory: 42656kb

input:

11111 100000

output:

111110
1 1
1 22221
1 44441
1 66661
1 88881
11102 100000
11111 77789
11111 55569
11111 33349
11111 11129
19 1
1 22203
1 44423
1 66643
1 88863
11084 100000
11111 77807
11111 55587
11111 33367
11111 11147
37 1
1 22185
1 44405
1 66625
1 88845
11066 100000
11111 77825
11111 55605
11111 33385
11111 11165
...

result:

ok n: 11111, m: 100000, bishops: 111110

Test #27:

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

input:

1 1

output:

1
1 1

result:

ok n: 1, m: 1, bishops: 1

Extra Test:

score: 0
Extra Test Passed