Submission #1052509

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052509		Ahmed57	Seats (IOI18_seats)	C++17	0 / 100	123 ms	22468 KiB

seats

#include "bits/stdc++.h"

using namespace std;
vector<int> c;
int pos[1000001];
int h,w , all = 0;
int cst[1000001];
void give_initial_chart(int H, int W, vector<int> R, vector<int> C){
    h = H;
    w = W;
    for(int i = 0;i<H*W;i++){
        c.push_back(C[i]);
    }
    for(int i = 0;i<H*W;i++){
        pos[c[i]] = i;
        int cost = 1-(c[i]>0&&pos[c[i]-1]<pos[c[i]])-(c[i]<W-1&&pos[c[i]+1]<pos[c[i]]);
        all+=cost;
        cst[c[i]] = cost;
    }
}
int swap_seats(int a, int b){
    set<int> s;
    s.insert(c[a]);
    s.insert(c[b]);
    if(c[a]>0)s.insert(c[a]-1);
    if(c[a]<w-1)s.insert(c[a]+1);
    if(c[b]>0)s.insert(c[b]-1);
    if(c[b]<w-1)s.insert(c[b]+1);
    for(auto i:s){
        all-=cst[i];
    }
    swap(c[a],c[b]);
    swap(pos[c[a]],pos[c[b]]);
    for(auto i:s){
        cst[i] = 1-(i>0&&pos[i-1]<pos[i])-(i<w-1&&pos[i+1]<pos[i]);
        all+=cst[i];
    }
    return all;
}

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