Letöltés: og_vonat.cpp #include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
struct menetrend
{
int mik,med;
char hon;
};
menetrend** a;
void beolvas(char*);
bool compare(menetrend, menetrend);
void docase(int);
void kiir(char*);
int n;
int* t;
int *na;
int *nb;
char c;
int* ki1;
int* ki2;
int main()
{
beolvas("tt-large.in");
ki1= new int[n];
ki2= new int[n];
for(int i=0; i<n; i++)
{
docase(i);
}
kiir("kimenet.out");
return 0;
}
void beolvas(char* file)
{
FILE* be = fopen(file, "r");
fscanf(be, "%d", &n);
a = new menetrend*[n+1];
t = new int[n+1];
na = new int[n+1];
nb = new int[n+1];
for(int i=0; i<n; i++)
{
fscanf(be, "%d", &t[i]);
t[i]=t[i];
fscanf(be, "%d %d", &na[i], &nb[i]);
a[i]= new menetrend[na[i]+nb[i]+1];
for(int j=0; j<na[i]; j++)
{
int temp1, temp2, temp3, temp4;
fscanf(be, "%d%c%d", &temp1, &c, &temp2);
fscanf(be, "%d%c%d", &temp3, &c, &temp4);
a[i][j].hon='A';
a[i][j].mik=60*temp1+temp2;
a[i][j].med=60*temp3+temp4;
}
for(int j=0; j<nb[i]; j++)
{
int temp1, temp2, temp3, temp4;
fscanf(be, "%d%c%d", &temp1, &c, &temp2);
fscanf(be, "%d%c%d", &temp3, &c, &temp4);
a[i][na[i]+j].hon='B';
a[i][na[i]+j].mik=60*temp1+temp2;
a[i][na[i]+j].med=60*temp3+temp4;
}
}
fclose(be);
return;
}
bool compare(menetrend x, menetrend y)
{
if(x.mik>=y.mik) return false;
return true;
}
void docase(int i)
{
sort(a[i], a[i]+na[i]+nb[i], compare);
int A=0; int B=0;
priority_queue<int, vector<int>, greater<int> > Aq;
priority_queue<int, vector<int>, greater<int> > Bq;
Aq.push(32000);
Bq.push(32000);
for(int j=0; j<na[i]+nb[i]; j++)
{
if(a[i][j].hon=='A')
{
if(Aq.top()>a[i][j].mik)
{
A++;
Bq.push(a[i][j].med+t[i]);
}
else
{
Aq.pop();
Bq.push(a[i][j].med+t[i]);
}
}
else if (a[i][j].hon=='B')
{
if(Bq.top()>a[i][j].mik)
{
B++;
Aq.push(a[i][j].med+t[i]);
}
else
{
Bq.pop();
Aq.push(a[i][j].med+t[i]);
}
}
else
{
cout << "ERROR!!!!!";
break;
}
}
ki1[i]=A;
ki2[i]=B;
return;
}
void kiir(char* file)
{
FILE* ki = fopen(file, "w");
for(int i=0; i<n; i++)
{
fprintf(ki,"Case #%d: %d %d\n",i+1,ki1[i],ki2[i]);
}
fclose(ki);
return;
}
|