Submission #1073803

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073803		HorizonWest	Seats (IOI18_seats)	C++17	5 / 100	4062 ms	184656 KiB

seats

#include <iostream>
#include <complex>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <functional>
#include <bitset>
#include <queue>
#include <map>
#include <stack>
#include <cmath>
#include <cstdint>
using namespace std;

#define endl '\n'
#define db double
#define ll long long
#define pb push_back
#define fs first
#define sd second
#define Mod long(1e9 + 7)
#define all(x) x.begin(), x.end()
#define unvisited long(-1)
#define Eps double(1e-9)
#define _for(i, n) for(int i = 0; i < (n); i++)
#define dbg(x) cout << #x ": " << x << endl;

const int Max = 1e6 + 7, Inf = 1e9 + 7;

struct rectangle{
    int a, b, c, d;

    rectangle(int i, int j, int k, int l){
        a = i; b =j; c = k; d = l; 
    }
};


vector <pair<int, int>> v; 
vector <rectangle> t; 
vector <int> s;

int m[5001][5001]; 

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) 
{
    int a = Inf, b = 0, c = Inf, d = 0;
    t.push_back({ a, b, c, d });
    s.push_back(0); 
    v.push_back({ 0, 0 });

    for(int i = 0; i < H*W; i++){
        v.push_back({ R[i], C[i] });
        a = min(a, v[i+1].fs);
        b = max(b, v[i+1].fs);
        c = min(c, v[i+1].sd);
        d = max(d, v[i+1].sd);
        t.push_back({ a, b, c, d });
        int fx = (b-a+1) * (d-c+1);
        s.push_back(0);
        s[i+1] += s[i] + ((i+1) == fx);
        m[R[i]][C[i]] = i+1;
    }
}

int tmp(int A, int B)
{
    A++; B++; swap(v[A], v[B]);
    int a = Inf, b = 0, c = Inf, d = 0, ans = 0;

    for(int i = 1; i < v.size(); i++)
    {
        a = min(a, v[i].fs);
        b = max(b, v[i].fs);
        c = min(c, v[i].sd);
        d = max(d, v[i].sd);
        int fx = (b-a+1) * (d-c+1);
        ///if(B == 7) cerr << a << " " << b << " " << c << " " << d << endl;
        ans += (fx == i);
    }
    //swap(v[A], v[B]);
    return ans;
}

int swap_seats(int A, int B) {
    return tmp(A, B);
    A++; B++;
    if(A > B) swap(A, B);

    int ans = s[A-1] + s.back() - s[B];
    int a = t[A-1].a, b = t[A-1].b, 
        c = t[A-1].c, d = t[A-1].d;

    swap(v[A], v[B]);

    for(int i = A; i <= B; i++){
        a = min(a, v[i].fs);
        b = max(b, v[i].fs);
        c = min(c, v[i].sd);
        d = max(d, v[i].sd);
        int fx = (b-a+1) * (d-c+1);
        ans += (i == fx);
    }

    swap(v[A], v[B]);

    return ans;
}

Compilation message (stderr)

seats.cpp: In function 'int tmp(int, int)':
seats.cpp:71:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(int i = 1; i < v.size(); i++)
      |                    ~~^~~~~~~~~~

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