Submission #91713

#	Time	Username	Problem	Language	Result	Execution time	Memory
91713		Retro3014	Seats (IOI18_seats)	C++17	17 / 100	4019 ms	61588 KiB

seats

#include "seats.h"
#include <vector>
#include <algorithm>
#include <iostream>


using namespace std;

struct S{
    int x, y;
};
int h, w;

vector<S> v;
vector<int> r;

vector<S> s, e;
int ans;


void pro1();
int solve1(int x, int y);
int solve2(int x, int y);
int solve3(int x, int y);

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    h=H; w=W;
    for(int i=0; i<R.size(); i++){
        v.push_back({R[i], C[i]});
    }
    pro1();
}

int swap_seats(int a, int b) {
    if(h*w<=10000){
        return solve1(a, b);
    }/*else if(h<=1000 && w<=1000){
        return solve2(a, b);
    }*/else{
        return solve3(a, b);
    }
}

void pro1(){
    ans=1;
    s.clear(); e.clear();
    s.push_back({v[0].x, v[0].y});
    e.push_back({v[0].x, v[0].y});
    for(int i=1; i<h*w; i++){
        s.push_back(s.back());
        e.push_back(e.back());
        s.back().x=min(s.back().x, v[i].x);
        s.back().y=min(s.back().y, v[i].y);
        e.back().x=max(e.back().x, v[i].x);
        e.back().y=max(e.back().y, v[i].y);
        if((e.back().x-s.back().x+1)*(e.back().y-s.back().y+1)==i+1){
            ans++;
        }
    }
    
}
int solve1(int x, int y){
    ans=0;
    S tmp=v[x]; v[x]=v[y]; v[y]=tmp;
    pro1();
    return ans;
}

int solve2(int x, int y){
    return 0;
}

int solve3(int x, int y){
    if(x>y){
        int tmp=x; x=y; y=tmp;
    }
    S tmp=v[x]; v[x]=v[y]; v[y]=tmp;
    for(int i=x; i<=y; i++){
        if((e[i].x-s[i].x+1)*(e[i].y-s[i].y+1)==i+1)    ans--;
        if(i==0){
            e[i].x=v[i].x; e[i].y=v[i].y;
            s[i].x=v[i].x; s[i].y=v[i].y;
        }else{
            e[i].x=max(e[i-1].x, v[i].x);
            e[i].y=max(e[i-1].y, v[i].y);
            s[i].x=min(s[i-1].x, v[i].x);
            s[i].y=min(s[i-1].y, v[i].y);
        }
        if((e[i].x-s[i].x+1)*(e[i].y-s[i].y+1)==i+1)    ans++;
    }
    return ans;
}

Compilation message (stderr)

seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:28:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<R.size(); i++){
                  ~^~~~~~~~~

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