Submission #1024245

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024245		ksu2009en	Seats (IOI18_seats)	C++17	0 / 100	4067 ms	135624 KiB

seats

#include "seats.h"
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <bitset>
#include <cstring>
#include <unordered_map>

using namespace std;
typedef int ll;

vector<pair<ll, ll>> d;

vector<ll> row, col;
set<ll> st1[1007], st2[1007];

ll n, m;

void give_initial_chart(int h, int w, std::vector<int> r, std::vector<int> c) {
    n = h, m = w;
    
    row.resize(h);
    col.resize(w);
    
    for(int i = h * w - 1; i >= 0; i--){
        row[r[i]] = i;
        col[c[i]] = i;
        
        st1[r[i]].insert(i);
        st2[c[i]].insert(i);
    }
    
    for(int i = 0; i < h * w; i++)
        d.push_back({r[i], c[i]});
}

int swap_seats(int a, int b) {
    st1[d[a].first].erase(a);
    st2[d[a].second].erase(a);
    
    st1[d[b].first].erase(b);
    st2[d[b].second].erase(b);
    
    swap(d[a], d[b]);
    
    st1[d[a].first].insert(a);
    st2[d[a].second].insert(a);
    
    st1[d[b].first].insert(b);
    st2[d[b].second].insert(b);
    
    row[d[a].first] = *st1[d[a].first].begin();
    col[d[a].second] = *st2[d[a].second].begin();
    
    row[d[b].first] = *st1[d[b].first].begin();
    col[d[b].second] = *st2[d[b].second].begin();
    
    vector<pair<ll, ll>> vec1, vec2;
    for(int i = 0; i < row.size(); i++)
        vec1.push_back({row[i], i});
    
    for(int i = 0; i < col.size(); i++)
        vec2.push_back({col[i], i});
    
    sort(vec1.begin(), vec1.end());
    sort(vec2.begin(), vec2.end());
    
//    for(auto i: vec2)
//        cout << i.first << ' ' << i.second << endl;
    
    ll mn1 = 0, mn2 = 0, mx1 = 0, mx2 = 0;
    ll cur = 0;
    // row col row col
    
    ll ans = 0;
    
    while(true){
        ll p1 = mn1, p2 = mn2, p3 = mx1, p4 = mx2;
        
        while(p1 < n && vec1[p1].second >= vec1[mn1].second)
            p1++;
        while(p2 < m && vec2[p2].second >= vec2[mn2].second)
            p2++;
        
        while(p3 < n && vec1[p3].second <= vec1[mx1].second)
            p3++;
        while(p4 < m && vec2[p4].second <= vec2[mx2].second)
            p4++;
//        cout << mn1 << ' ' << mn2 << ' ' << mx1 << ' ' << mx2 << endl;
//        cout << p1 << ' ' << p2 << ' ' << p3 << ' ' << p4 << endl;
                
        ll next0 = n * m;
        if(p1 < n)
            next0 = min(next0, vec1[p1].first);
        if(p2 < m)
            next0 = min(next0, vec2[p2].first);
        if(p3 < n)
            next0 = min(next0, vec1[p3].first);
        if(p4 < m)
            next0 = min(next0, vec2[p4].first);
        
        ll area = (vec1[mx1].second - vec1[mn1].second + 1) * (vec2[mx2].second - vec2[mn2].second + 1);
        //cout << area << ' ' << next0 << endl;
        if(area >= cur && area <= next0)
            ans++;
        
        if(next0 == vec1[p1].first)
            mn1 = p1;
        if(next0 == vec2[p2].first)
            mn2 = p2;
        
        if(next0 == vec1[p3].first)
            mx1 = p3;
        if(next0 == vec2[p4].first)
            mx2 = p4;
        
        if(p1 == n && p2 == m && p3 == n && p4 == m)
            break;
    }
    
    return ans;
}
/*
 2 3 2
 0 0
 1 0
 1 1
 0 1
 0 2
 1 2
 0 5
 0 5
 
 */

Compilation message (stderr)

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

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