Submission #599913

#	Time	Username	Problem	Language	Result	Execution time	Memory
599913		Hanksburger	Seats (IOI18_seats)	C++17	25 / 100	2155 ms	120004 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
set<int> xs[1005], ys[1005];
vector<int> x, y;
int n, m;
void give_initial_chart(int N, int M, vector<int> X, vector<int> Y)
{
    n=N;
    m=M;
    x=X;
    y=Y;
    for (int i=0; i<n*m; i++)
    {
        xs[x[i]].insert(i);
        ys[y[i]].insert(i);
    }
}
int swap_seats(int a, int b)
{
    if (a>b)
        swap(a, b);
    xs[x[a]].erase(a);
    ys[y[a]].erase(a);
    xs[x[b]].erase(b);
    ys[y[b]].erase(b);
    swap(x[a], x[b]);
    swap(y[a], y[b]);
    xs[x[a]].insert(a);
    ys[y[a]].insert(a);
    xs[x[b]].insert(b);
    ys[y[b]].insert(b);
    vector<pair<int, pair<int, int> > > v;
    for (int i=0; i<n; i++)
        v.push_back({*xs[i].begin(), {0, i}});
    for (int i=0; i<m; i++)
        v.push_back({*ys[i].begin(), {1, i}});
    sort(v.begin(), v.end());
    int xmn=1e9, xmx=-1, ymn=1e9, ymx=-1, ans=1;
    for (int i=0; i<v.size(); i++)
    {
        if (v[i].first==v[i+1].first)
        {
            xmn=min(xmn, v[i].second.second);
            xmx=max(xmx, v[i].second.second);
            i++;
            ymn=min(ymn, v[i].second.second);
            ymx=max(ymx, v[i].second.second);
        }
        else if (v[i].second.first)
        {
            ymn=min(ymn, v[i].second.second);
            ymx=max(ymx, v[i].second.second);
        }
        else
        {
            xmn=min(xmn, v[i].second.second);
            xmx=max(xmx, v[i].second.second);
        }
        if (i+2<=v.size() && (xmx-xmn+1)*(ymx-ymn+1)<=v[i+1].first)
            ans++;
    }
    return ans;
}

Compilation message (stderr)

seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:40:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for (int i=0; i<v.size(); i++)
      |                   ~^~~~~~~~~
seats.cpp:60:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         if (i+2<=v.size() && (xmx-xmn+1)*(ymx-ymn+1)<=v[i+1].first)
      |             ~~~^~~~~~~~~~

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