oj.uz

Submission #1080229

# Submission time Handle Problem Language Result Execution time Memory
1080229 2024-08-29T08:09:08 Z Evirir Abduction 2 (JOI17_abduction2) C++17
27 / 100
 542 ms 524288 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define cbug if(DEBUG) cout
#define setp(x) cout<<fixed<<setprecision(x)
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define forn(i,a,b) for(int i=(a);i<(b);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define F first
#define S second
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
//template<typename T>
//using pbds = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
void SD(int t=0){ cout<<"PASSED "<<t<<endl; }
ostream& operator<<(ostream &out, ii x){ out<<"("<<x.F<<","<<x.S<<")"; return out; }
template<typename T> void amax(T &a, T b){ a=max(a,b); }
template<typename T> void amin(T &a, T b){ a=min(a,b); }
struct Hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

const ll INF = ll(1e18);
const int MOD = 998244353;
const bool DEBUG = 0;
const int MAXN = 100005;
const int LG = 21;

constexpr ii del[] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

int n,m,Q;
vector<int> a, b, dp;
vector<bool> vst;

void read()
{
    cin>>n>>m>>Q;
    a.resize(n); b.resize(m);
    forn(i,0,n) cin>>a[i];
    forn(i,0,m) cin>>b[i];
    vector<int> v(all(a));
    for (const auto x : b) v.pb(x);
    sort(all(v));
    unordered_map<int, int> mp;
    forn(i,0,sz(v)) mp[v[i]] = i;
    for (auto& x : a) x = mp[x];
    for (auto& x : b) x = mp[x];
}

int getid(int x, int y, int d)
{
    return (x * m + y) * 4 + d;
}

array<int, 3> unid(int id)
{
    int d = id % 4;
    id /= 4;
    int y = id % m;
    int x = id /= m;
    return {x, y, d};
}

bool oob(int x, int y)
{
    return min(x, y) < 0 || x >= n || y >= m;
}

using Nodes = vector<array<int, 3>>;

Nodes getadj(int i, int j, int d)
{
    auto [dx, dy] = del[d];
    int x1 = i + dx, y1 = j + dy;
    if (oob(x1, y1)) return {};
    bool chg;
    if (d <= 1) chg = b[j] < a[x1];
    else chg = a[i] < b[y1];
    if (!chg) return {{x1, y1, d}};
    else return {{x1, y1, d ^ 2}, {x1, y1, d ^ 3}};
}

void dfs(int x, int y, int d)
{
    int u = getid(x, y, d);
    if (vst[u]) return;
    vst[u] = 1;

    Nodes adj = getadj(x, y, d);
    for (const auto& [x1, y1, d1] : adj)
    {
        int v = getid(x1, y1, d1);
        if (!vst[v]) dfs(x1, y1, d1);
        dp[u] = max(dp[u], dp[v] + 1);
    }
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);

    read();
    int ncnt = n * m * 4;

    dp.resize(ncnt);
    vst.resize(ncnt);
    forn(i,0,n) forn(j,0,m) forn(d,0,4)
    {
        int id = getid(i, j, d);
        if (vst[id]) continue;
        dfs(i, j, d);
    }

    forn(z,0,Q)
    {
        int x,y; cin>>x>>y; x--; y--;
        int ans = 0;
        forn(d,0,4)
        {
            int id = getid(x, y, d);
            ans = max(ans, dp[id]);
        }
        cout << ans << '\n';
    }

    // cout<<"dp:\n";
    // forn(i,0,n) forn(j,0,m) forn(d,0,4)
    // {
    //     int id = getid(i, j, d);
    //     cout << "(" << i << "," << j << "," << d << ") -> " << dp[id] << '\n';
    // }
    // cout<<'\n';
    // cout<<"adj:\n";
    // forn(i,0,n) forn(j,0,m) forn(d,0,4)
    // {
    //     int id = getid(i, j, d);
    //     cout << "(" << i << "," << j << "," << d << ") ->";
    //     for (const auto v : adj[id])
    //     {
    //         auto [i1, j1, d1] = unid(v);
    //         cout<<' '<<" (" << i1 << ',' << j1 << ',' << d1 << ")";
    //     }
    //     cout<<'\n';
    // }

    return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 517 ms 65648 KB Output is correct
13 Correct 522 ms 65364 KB Output is correct
14 Correct 524 ms 65692 KB Output is correct
15 Correct 529 ms 65668 KB Output is correct
16 Correct 515 ms 65616 KB Output is correct
17 Correct 488 ms 65872 KB Output is correct
18 Correct 484 ms 65872 KB Output is correct
19 Correct 499 ms 66136 KB Output is correct
20 Correct 512 ms 64216 KB Output is correct
21 Correct 514 ms 64848 KB Output is correct
22 Correct 478 ms 66204 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 517 ms 65648 KB Output is correct
13 Correct 522 ms 65364 KB Output is correct
14 Correct 524 ms 65692 KB Output is correct
15 Correct 529 ms 65668 KB Output is correct
16 Correct 515 ms 65616 KB Output is correct
17 Correct 488 ms 65872 KB Output is correct
18 Correct 484 ms 65872 KB Output is correct
19 Correct 499 ms 66136 KB Output is correct
20 Correct 512 ms 64216 KB Output is correct
21 Correct 514 ms 64848 KB Output is correct
22 Correct 478 ms 66204 KB Output is correct
23 Runtime error 266 ms 524288 KB Execution killed with signal 9
24 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 511 ms 65656 KB Output is correct
2 Correct 520 ms 65616 KB Output is correct
3 Correct 537 ms 65664 KB Output is correct
4 Correct 539 ms 65364 KB Output is correct
5 Correct 542 ms 65928 KB Output is correct
6 Correct 481 ms 65880 KB Output is correct
7 Correct 494 ms 65932 KB Output is correct
8 Correct 511 ms 66132 KB Output is correct
9 Correct 509 ms 65084 KB Output is correct
10 Correct 512 ms 65620 KB Output is correct
11 Correct 486 ms 66140 KB Output is correct

Subtask #5
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 517 ms 65648 KB Output is correct
13 Correct 522 ms 65364 KB Output is correct
14 Correct 524 ms 65692 KB Output is correct
15 Correct 529 ms 65668 KB Output is correct
16 Correct 515 ms 65616 KB Output is correct
17 Correct 488 ms 65872 KB Output is correct
18 Correct 484 ms 65872 KB Output is correct
19 Correct 499 ms 66136 KB Output is correct
20 Correct 512 ms 64216 KB Output is correct
21 Correct 514 ms 64848 KB Output is correct
22 Correct 478 ms 66204 KB Output is correct
23 Runtime error 266 ms 524288 KB Execution killed with signal 9
24 Halted 0 ms 0 KB -