Codeforces 1236 #Codeforces

1236C.cpp

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

const ll inf=0x3f3f3f3f3f3f3f3f;

void redirect_input(){freopen("./input.txt","r",stdin);}
void redirect_output(){freopen("./output.txt","w",stdout);}

const int maxn = 1e5 + 1000;
const ll mod = 1e9 + 7;
vector<int> ans[350];

void solve(){
    int n, lim;
    cin >> n;
    lim = n * n;
    for(int i=0; i<lim; i++){
        int pos = i % (2 * n);
        if(pos >= n) pos = 2 * n - pos - 1;
        ans[pos].push_back(i);
        // cout << "push " << i << " in " << pos << endl;
    }
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cout << (ans[i][j] + 1) << ' ';
        }
        cout << '\n';
    }
}

signed main(){
    Android;

    solve();
}

1236D.cpp

#include <bits/stdc++.h>
#define ll long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

const int maxn = 1e5 + 1000;

set<int> row[maxn];
set<int> col[maxn];
ll n, m, k;

ll walk(){
    int cur_r = 1, cur_c = 1, ori_x = 0, ori_y = 1;
    int direction = 0;
    int mx_r = n + 1, mn_r = 1;
    int mx_c = m + 1, mn_c = 0;
    ll step = 1;
    bool is_first_step = true; // 第一步有额外的右转机会
    while(true){
        // cerr << cur_r << " : " << cur_c << " dir " << direction << endl;
        int nx_r = cur_r, nx_c = cur_c;
        if(direction==0)
            mx_c = nx_c = max(cur_c, min(mx_c-1, *row[cur_r].upper_bound(cur_c)-1));
        if(direction==1)
            mx_r = nx_r = max(cur_r, min(mx_r-1, *col[cur_c].upper_bound(cur_r)-1));
        if(direction==2)
            mn_c = nx_c = min(cur_c, max(mn_c+1, *prev(row[cur_r].upper_bound(cur_c))+1));
        if(direction==3)
            mn_r = nx_r = min(cur_r, max(mn_r+1, *prev(col[cur_c].upper_bound(cur_r))+1));

        step += abs(nx_r - cur_r) + abs(nx_c - cur_c);
        direction = (1 + direction) % 4;
        if(cur_c == nx_c && cur_r == nx_r && !is_first_step) break;
        ori_x = cur_r, ori_y = cur_c;
        cur_r = nx_r, cur_c = nx_c;
        is_first_step = false;
    }
    return step;
}

void solve(){
    cin >> n >> m >> k;
    for(int i=0; i<k; i++){
        int x, y;
        cin >> x >> y;
        row[x].insert(y);
        col[y].insert(x);
    }
    for(int i=0; i<=n; i++) row[i].insert(0), row[i].insert(m+1);
    for(int i=0; i<=m; i++) col[i].insert(0), col[i].insert(n+1);
    ll step = walk();
    cout << (step >= n * m - k?"Yes":"No") << '\n';
}

signed main(){
    Android;
    solve();
}