제출 #599914

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
599914		Hanksburger	자리 배치 (IOI18_seats)	C++17	37 / 100	4053 ms	117924 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> x, y, xmn, ymn, xmx, ymx;
set<int> xs[1005], ys[1005];
int n, m, sum;
void give_initial_chart(int N, int M, vector<int> X, vector<int> Y)
{
    n=N;
    m=M;
    x=X;
    y=Y;
    if (n<=1000 && m<=1000)
    {
        for (int i=0; i<n*m; i++)
        {
            xs[x[i]].insert(i);
            ys[y[i]].insert(i);
        }
    }
    else
    {
        for (int i=0; i<n*m; i++)
        {
            if (!i)
            {
                xmn.push_back(x[i]);
                ymn.push_back(y[i]);
                xmx.push_back(x[i]);
                ymx.push_back(y[i]);
            }
            else
            {
                xmn.push_back(min(xmn[i-1], x[i]));
                ymn.push_back(min(ymn[i-1], y[i]));
                xmx.push_back(max(xmx[i-1], x[i]));
                ymx.push_back(max(ymx[i-1], y[i]));
            }
            sum+=((xmx[i]-xmn[i]+1)*(ymx[i]-ymn[i]+1)==i+1);
        }
    }
}
int swap_seats(int a, int b)
{
    if (a>b)
        swap(a, b);
    if (n<=1000 && m<=1000)
    {
        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;
    }
    else
    {
        for (int i=a; i<b; i++)
            sum-=((xmx[i]-xmn[i]+1)*(ymx[i]-ymn[i]+1)==i+1);
        swap(x[a], x[b]);
        swap(y[a], y[b]);
        for (int i=a; i<b; i++)
        {
            if (!i)
            {
                xmn[i]=x[i];
                ymn[i]=y[i];
                xmx[i]=x[i];
                ymx[i]=y[i];
            }
            else
            {
                xmn[i]=min(xmn[i-1], x[i]);
                ymn[i]=min(ymn[i-1], y[i]);
                xmx[i]=max(xmx[i-1], x[i]);
                ymx[i]=max(ymx[i-1], y[i]);
            }
            sum+=((xmx[i]-xmn[i]+1)*(ymx[i]-ymn[i]+1)==i+1);
        }
        return sum;
    }
}

컴파일 시 표준 에러 (stderr) 메시지

seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:66:24: 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]
   66 |         for (int i=0; i<v.size(); i++)
      |                       ~^~~~~~~~~
seats.cpp:86: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]
   86 |             if (i+2<=v.size() && (Xmx-Xmn+1)*(Ymx-Ymn+1)<=v[i+1].first)
      |                 ~~~^~~~~~~~~~

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