Submission #600780

#	Time	Username	Problem	Language	Result	Execution time	Memory
600780		Mazaalai	Seats (IOI18_seats)	C++17	0 / 100	4009 ms	43692 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define chmax(a, b) a = max(a, b)
#define sz(x) (int)x.size()
using namespace std;
using VI = vector <int>;
vector <vector <int> > nums;
vector <vector <int> > dp;
vector <int> r;
vector <int> c;
int n, m;
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    r = R, c = C;
    n = H;
    m = W;
    nums = vector <VI>(n, VI(m));
    for (int i = 0; i < n*m; i++) 
        nums[R[i]][C[i]] = i;
    
}

int swap_seats(int a, int b) {
    // cout << "HELLO\n";
    swap(nums[r[a]][c[a]], nums[r[b]][c[b]]);
    swap(r[a], r[b]);
    swap(c[a], c[b]);
    dp = nums;
    int x = r[0], y = c[0], ans = 0;
    for (int i = 0; i < n; i++) 
    for (int j = 0; j < m; j++) {
        for (int A = -1; A <= 1; A+=2)
        for (int B = -1; B <= 1; B+=2) {
            int a = x+A*i;
            int b = y+B*j;
            if (0 <= a && a < n && 0 <= b && b < m) 
                dp[a][b] = max({dp[a][b], (j==0 ? 0 : dp[a][b-B]), (i==0 ? 0 : dp[a-A][b])});
            
        }
    }
    for (int i = 0; i < n; i++) 
    for (int j = 0; j < m; j++) {
        int a = abs(x-i);
        int b = abs(y-j);
        // cout << i << " " << j << ' ' << x << ' ' << y << " -> " << a+1 << ' ' << b+1 << ' ' << dp[i][j] << " ," << (dp[i][j]+1 == (a+1)*(b+1)) << '\n';
        ans += ((dp[i][j]+1) == (a+1)*(b+1));
    }
    return ans;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30