QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#175780#7178. Bishopsucup-team1231#TL 8ms40624kbC++142.5kb2023-09-10 23:32:362023-09-10 23:32:37

Judging History

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

  • [2023-09-10 23:32:37]
  • 评测
  • 测评结果:TL
  • 用时:8ms
  • 内存:40624kb
  • [2023-09-10 23:32:36]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pii;
#define mp make_pair
#define pb push_back

map<pii,int> M;
vi a[500000],b[500000];
vi adj[500000];
int visited[500000];
int keep[500000];
int main() {
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(0);
    int n,m;
    cin >> n >> m;

    int i;
    if (n == 1) {
        cout << m << endl;
        for (i = 0; i < m; i++) cout << 1 << " " << i+1 << endl;
        return 0;
    }
    else if (m == 1) {
        cout << n << endl;
        for (i = 0; i < n; i++) cout << i+1 << " " << 1 << endl;
        return 0;
    }

    int c = 0;
    for (i = 0; i < m; i++) M[mp(0,i)] = c++;
    for (i = 1; i < n-1; i++) M[mp(i,0)] = c++;
    for (i = 0; i < m; i++) M[mp(n-1,i)] = c++;
    for (i = 1; i < n-1; i++) M[mp(i,m-1)] = c++;
    for (auto [p,x]: M) {
        a[p.first+p.second].pb(x);
        b[p.first-p.second+m].pb(x);
    }
    for (i = 0; i < 500000; i++) {
        if (a[i].size() >= 2) {
            adj[a[i][0]].pb(a[i][1]);
            adj[a[i][1]].pb(a[i][0]);
        }
        if (b[i].size() >= 2) {
            adj[b[i][0]].pb(b[i][1]);
            adj[b[i][1]].pb(b[i][0]);
        }
    }
    int j,ans = 0;
    for (i = 0; i < c; i++) {
        if (!visited[i] && (adj[i].size() <= 1)) {
            int u = i;
            vi o;
            do {
                int f = 0;
                visited[u] = 1;
                o.pb(u);
                for (int v: adj[u]) {
                    if (!visited[v]) {
                        u = v;
                        f = 1;
                        break;
                    }
                }
                if (!f) break;
            } while (u != i);
            for (j = 0; j < o.size(); j += 2) keep[o[j]] = 1,ans++;
        }
    }
    for (i = 0; i < c; i++) {
        if (!visited[i]) {
            int u = i;
            vi o;
            do {
                int f = 0;
                visited[u] = 1;
                o.pb(u);
                for (int v: adj[u]) {
                    if (!visited[v]) {
                        u = v;
                        f = 1;
                        break;
                    }
                }
                if (!f) break;
            } while (u != i);
            for (j = 0; j < o.size(); j += 2) keep[o[j]] = 1,ans++;
        }
    }
    cout << ans << endl;
    for (auto [p,x]: M) {
        if (keep[x]) cout << p.first+1 << " " << p.second+1 << endl;
    }


    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 8ms
memory: 40624kb

input:

2 5

output:

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

result:

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

Test #2:

score: 0
Accepted
time: 7ms
memory: 39592kb

input:

5 5

output:

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

result:

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

Test #3:

score: -100
Time Limit Exceeded

input:

100000 100000

output:

199998
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: