Submission #684098

# Submission time Handle Problem Language Result Execution time Memory
684098 2023-01-20T11:11:26 Z nifeshe Ants (IZhO12_ants) C++17
100 / 100
1 ms 448 KB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC target ("avx2")
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
//#pragma comment (linker, "/STACK: 16777216")

#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define pb push_back
#define mp make_pair
//#define int long long

using namespace std;
using namespace __gnu_pbds;

template <typename T> inline bool umax(T &a, const T &b) { if(a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool umin(T &a, const T &b) { if(a > b) { a = b; return 1; } return 0; }
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> using oset = tree<T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

ll mod = 998244353;
const ll base = 1e6 + 5;
const ll inf = 1e9 + 5;
const int MAX = 1e6 + 5;
const int LG = 31;

random_device rd;
mt19937 gen(rd());
uniform_int_distribution<ll> dis(1, inf);

vector<array<int, 3>> go(vector<array<int, 3>> pos, int n, int time) {
    sort(all(pos));
    vector<array<int, 3>> np;
    for(auto [x, d, idx] : pos) {
        x = (x + time * d) % (2 * n);
        if(x < 0) x += 2 * n;
        if(x > n) {
            x = 2 * n - x;
            d *=- 1;
        }
        if(!x) d = 1;
        else if(x == n) d = -1;
        np.pb({x, d, idx});
    }
    sort(all(np));
    for(int i = 0; i < sz(np); i++) {
        pos[i][0] = np[i][0];
        pos[i][1] = np[i][1];
    }
    return pos;
}

void solve() {
    int n, m, k, t;
    cin >> n >> m >> k >> t;
    vector<pair<int, int>> a(k);
    vector<vector<array<int, 3>>> x(n), y(m);
    for(int i = 0; i < k; i++) {
        int X, Y, d;
        cin >> X >> Y >> d;
        a[i] = {X, Y};
        if(d == 2)  x[X].pb({Y, 1, i});
        else if(d == 4)  x[X].pb({Y, -1, i});
        else if(d == 1)  y[Y].pb({X, 1, i});
        else if(d == 3)  y[Y].pb({X, -1, i});
    }
    vector<array<int, 3>> ans(k);
    for(int i = 0; i < n; i++) {
        auto curr = go(x[i], m, t);
        for(auto [Y, d, idx] : curr) ans[idx] = {a[idx].f, Y, ~d? 2 : 4};
    }
    for(int j = 0; j < m; j++) {
        auto curr = go(y[j], n, t);
        for(auto [X, d, idx] : curr) ans[idx] = {X, a[idx].s, ~d? 1 : 3};
    }
    for(auto [X, Y, d] : ans) {
        cout << X << " " << Y << " " << d << '\n';
    }
}

/*
5 5 2 1
3 4 4
3 3 4
*/

signed main() {
//    freopen("skyline.in", "r", stdin); freopen("skyline.out", "w", stdout);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int ttt = 1;
//    cin >> ttt;
    while(ttt--) {
        solve();
    }
    return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 448 KB Output is correct
19 Correct 0 ms 336 KB Output is correct
20 Correct 0 ms 340 KB Output is correct