Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #pragma comment(linker, "/stack:16777216")
- #include <string>
- #include <vector>
- #include <map>
- #include <list>
- #include <iterator>
- #include <cassert>
- #include <set>
- #include <queue>
- #include <iostream>
- #include <sstream>
- #include <stack>
- #include <deque>
- #include <cmath>
- #include <memory.h>
- #include <cstdlib>
- #include <cstdio>
- #include <cctype>
- #include <algorithm>
- #include <utility>
- #include <time.h>
- #include <complex>
- using namespace std;
- #define FOR(i, a, b) for(int i=(a);i<(b);i++)
- #define RFOR(i, b, a) for(int i=(b)-1;i>=(a);--i)
- #define FILL(A,value) memset(A,value,sizeof(A))
- #define ALL(V) V.begin(), V.end()
- #define SZ(V) (int)V.size()
- #define PB push_back
- #define MP make_pair
- #define Pi 3.14159265358979
- #define x0 ikjnrmthklmnt
- #define y0 lkrjhkltr
- #define y1 ewrgrg
- typedef long long Int;
- typedef unsigned long long UInt;
- typedef vector<int> VI;
- typedef pair<int, int> PII;
- typedef pair<Int, Int> PLL;
- typedef pair<double, double> PDD;
- typedef complex<double> base;
- const int INF = 1000000000;
- const int BASE = 1000000000;
- const int MAX = 107;
- const int MAX2 = 7777;
- const int MAXE = 100000;
- const int ADD = 1000000;
- const int MOD = 1000000007;
- const int CNT = 800;
- vector<int> W;
- int n , m , k , t , c;
- int p;
- struct Shop
- {
- int x , y;
- vector<int> a;
- friend istream & operator>>(istream & in, Shop & s)
- {
- in >> s.x >> s.y;
- s.a.resize(p);
- FOR(i,0,p)
- {
- in >> s.a[i];
- }
- return in;
- }
- };
- struct Order
- {
- int x , y;
- int id;
- vector<int> p;
- friend istream & operator>>(istream & in, Order & o)
- {
- in >> o.x >> o.y;
- int t;
- in >> t;
- FOR(i,0,t)
- {
- int x;
- in >> x;
- o.p.push_back(x);
- }
- return in;
- }
- int TotalWeight()
- {
- int r = 0;
- FOR(i,0,p.size())
- {
- r += W[p[i]];
- }
- return r;
- }
- };
- vector<Shop> S;
- vector<Order> O;
- int Sqrt(int x)
- {
- int y = sqrt(1.0 * x);
- while (y * y < x) ++y;
- return y;
- }
- int dist(int x1, int y1 , int x2 , int y2)
- {
- return Sqrt( (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) );
- }
- bool Comp(Order & a , Order & b)
- {
- int t1 = dist(a.x , a.y , S[0].x , S[0].y) + a.p.size();
- int t2 = dist(b.x , b.y , S[0].x , S[0].y) + b.p.size();
- int c1 = (a.TotalWeight() + c - 1) / c;
- int c2 = (b.TotalWeight() + c - 1) / c;
- return MP(c1 , t1) < MP(c2 , t2);
- }
- struct Command
- {
- int drone;
- char ch;
- int a , b , c;
- Command() {}
- Command(int _d, char _ch, int _a, int _b, int _c)
- {
- drone = _d;
- ch = _ch;
- a = _a;
- b = _b;
- c = _c;
- }
- friend ostream & operator<<(ostream & out , const Command & cmd)
- {
- out << cmd.drone << ' ' << cmd.ch << ' ' << cmd.a << ' ' << cmd.b << ' ' << cmd.c;
- return out;
- }
- };
- vector<Command> res;
- set<PII> Drones;
- int curTime;
- bool RunCommand(int time , int drone, int order, vector<int> & p)
- {
- int tt = dist(S[0].x , S[0].y , O[order].x , O[order].y) + 2 * p.size();
- bool ok = 1;
- FOR(i,0,p.size())
- {
- S[0].a[p[i]]--;
- if (S[0].a[p[i]] < 0)
- {
- ok = 0;
- }
- }
- if (time + tt > t) ok = 0;
- if (!ok)
- {
- FOR(i,0,p.size())
- {
- S[0].a[p[i]]++;
- }
- }
- if (ok)
- {
- for(int i = 0; i < p.size(); ++i)
- {
- res.push_back(Command(drone , 'L', 0, p[i], 1));
- }
- for(int i = 0; i < p.size(); ++i)
- {
- res.push_back(Command(drone , 'D', order, p[i], 1));
- }
- curTime = time + tt;
- Drones.insert( MP( time + tt + dist(S[0].x , S[0].y , O[order].x , O[order].y) , drone) );
- return 1;
- }
- else
- {
- Drones.insert(MP(time, drone));
- return 0;
- }
- }
- int main()
- {
- freopen("in.txt", "r", stdin);
- //freopen("distance.in", "r", stdin);
- //freopen("distance.out", "w", stdout);
- freopen("out.txt" , "w" , stdout);
- cin >> n >> m >> k >> t >> c;
- cin >> p;
- W.resize(p);
- FOR(i,0,p)
- {
- cin >> W[i];
- }
- int s;
- cin >> s;
- S.resize(s);
- FOR(i,0,s)
- {
- cin >> S[i];
- }
- int o;
- cin >> o;
- O.resize(o);
- FOR(i,0,o)
- {
- cin >> O[i];
- O[i].id = i;
- }
- sort(ALL(O), Comp);
- int score = 0;
- FOR(i,0,k)
- {
- Drones.insert(MP(0, i));
- }
- for(int i = 0; i < O.size(); ++i)
- {
- vector<VI> A;
- random_shuffle(ALL(O[i].p));
- int curw = 0;
- VI B;
- FOR(j,0,O[i].p.size())
- {
- if (curw + W[O[i].p[j]] > c)
- {
- A.push_back(B);
- B.clear();
- B.push_back(W[O[i].p[j]]);
- curw = W[O[i].p[j]];
- }
- else
- {
- B.push_back(W[O[i].p[j]]);
- curw += W[O[i].p[j]];
- }
- }
- A.push_back(B);
- bool ok = 1;
- FOR(j,0,A.size())
- {
- PII d = *Drones.begin();
- Drones.erase(Drones.begin());
- ok &= RunCommand(d.first , d.second, O[i].id, A[j]);
- if (!ok) break;
- }
- if (ok)
- {
- score += (100 * (t - curTime) + t - 1) / t;
- }
- }
- cout << res.size() << endl;
- FOR(i,0,res.size())
- {
- cout << res[i] << endl;
- }
- cerr << score << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement