Submission #408672

#	Time	Username	Problem	Language	Result	Execution time	Memory
408672		MKopchev	Seats (IOI18_seats)	C++14	11 / 100	4080 ms	36024 KiB

seats

#include "seats.h"
#include<bits/stdc++.h>
using namespace std;

namespace {

int read_int() {
  int x;
  if (scanf("%d", &x) != 1) {
    fprintf(stderr, "Error while reading input\n");
    exit(1);
  }
  return x;
}

}  // namespace

const int nmax=1e6+42;

int n,m;

pair<int,int> where[nmax];

vector< vector<int> > inp;

pair<int,int> cnt[nmax];

int ask(int x,int y)
{
    if(0>x||x>=n||0>y||y>=m)return 1e9;
    return inp[x][y];
}
void eval(int x,int y)
{
    if(0>x||x>=n||0>y||y>=m)return;

    int cur[5]={0,0,0,0,0};

    int help;

    help=1+(ask(x-1,y-1)<inp[x][y])+(ask(x-1,y)<inp[x][y])+(ask(x,y-1)<inp[x][y]);
    cur[help]++;

    help=1+(ask(x-1,y)<inp[x][y])+(ask(x-1,y+1)<inp[x][y])+(ask(x,y+1)<inp[x][y]);
    cur[help]++;

    help=1+(ask(x,y-1)<inp[x][y])+(ask(x+1,y-1)<inp[x][y])+(ask(x+1,y)<inp[x][y]);
    cur[help]++;

    help=1+(ask(x,y+1)<inp[x][y])+(ask(x+1,y+1)<inp[x][y])+(ask(x+1,y)<inp[x][y]);
    cur[help]++;

    cnt[inp[x][y]]={cur[1]-cur[2],cur[3]-cur[4]};
    /*
    for(int i=0;i<5;i++)
        cnt[inp[x][y]][i]=0;

    for(int i=1;i<5;i++)
    {
        cnt[inp[x][y]][i]+=cur[i];
        cnt[inp[x][y]][i-1]-=cur[i];
    }
    */
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C)
{
    n=H;
    m=W;

    for(int t=0;t<n*m;t++)
    {
        int i=R[t];
        int j=C[t];

        while(inp.size()<=i)inp.push_back({});
        while(inp[i].size()<=j)inp[i].push_back(j);

        where[t]={i,j};
        inp[i][j]=t;
    }

    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            eval(i,j);
}

int swap_seats(int a, int b)
{
    swap(inp[where[a].first][where[a].second],inp[where[b].first][where[b].second]);
    swap(where[a],where[b]);

    for(int x=-1;x<=1;x++)
        for(int y=-1;y<=1;y++)
        {
            eval(where[a].first+x,where[a].second+y);
            eval(where[b].first+x,where[b].second+y);
        }

    pair<int,int> pref={0,0};

    int outp=0;

    for(int i=0;i<n*m;i++)
    {
        pref={pref.first+cnt[i].first,pref.second+cnt[i].second};

        if(pref.first==4&&pref.second==0)outp++;

        //cout<<"i: "<<i<<" pref: ";cout<<pref.first<<" "<<pref.second<<endl;
    }

    return outp;
}
/*
int main() {
  int H = read_int();
  int W = read_int();
  int Q = read_int();
  std::vector<int> R(H * W), C(H * W);
  for (int i = 0; i < H * W; ++i) {
    R[i] = read_int();
    C[i] = read_int();
  }
  std::vector<int> A(Q), B(Q);
  for (int j = 0; j < Q; ++j) {
    A[j] = read_int();
    B[j] = read_int();
  }

  give_initial_chart(H, W, R, C);
  for (int j = 0; j < Q; ++j) {
    int answer = swap_seats(A[j], B[j]);
    printf("%d\n", answer);
  }
  return 0;
}
*/

Compilation message (stderr)

seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:75:25: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   75 |         while(inp.size()<=i)inp.push_back({});
      |               ~~~~~~~~~~^~~
seats.cpp:76:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   76 |         while(inp[i].size()<=j)inp[i].push_back(j);
      |               ~~~~~~~~~~~~~^~~
seats.cpp: At global scope:
seats.cpp:7:5: warning: 'int {anonymous}::read_int()' defined but not used [-Wunused-function]
    7 | int read_int() {
      |     ^~~~~~~~

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