Submission #1080229

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080229		Evirir	Abduction 2 (JOI17_abduction2)	C++17	27 / 100	542 ms	524288 KiB

abduction2

#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 / 13
• Subtask 2: 10 / 10
• Subtask 3: 0 / 17
• Subtask 4: 4 / 4
• Subtask 5: 0 / 56