Untitled
unknown
plain_text
5 months ago
4.9 kB
8
Indexable
#include<iostream> #include<vector> #include<unordered_map> #include<set> #include<iterator> using namespace std; struct comp { bool operator()(const pair<int, int> &a, const pair<int, int> &b) const{ if ((a.second - a.first) > (b.second - b.first)) return true; else if (a.second - a.first == b.second - b.first) return(a.first < b.first); else return false; } }; int n; set<pair<int, int>, comp> empty_space; set<pair<int, int>> interval; unordered_map<int, int> building; void init(int N) { n = N; empty_space.clear(); building.clear(); interval.clear(); empty_space.insert({ 0,N - 1 }); interval.insert({ 0,N - 1 }); } int build(int mLength) { int address; set<pair<int, int>, comp> ::iterator it = empty_space.begin(); int start = it->first; int end = it->second; int spacelength = end - start +1 ; if (spacelength < mLength) return -1; address = start + ((spacelength - mLength) / 2); building[address] = mLength; empty_space.erase({ start,end }); interval.erase({ start,end }); empty_space.insert({ start, address - 1 }); empty_space.insert({ address + mLength,end }); interval.insert({ start, address - 1 }); interval.insert({ address + mLength,end }); return address; } int demolish(int mAddr) { if (building.find(mAddr) != building.end()) { int length = building[mAddr]; int new_start, new_end; building.erase(mAddr); int start = mAddr; int end = mAddr + length - 1; if (empty_space.empty()) { empty_space.insert({ start,end }); interval.insert({ start,end }); return length; } set<pair<int, int>> ::iterator it1 = interval.lower_bound({ start,end }); set<pair<int, int>> ::iterator it2 = interval.upper_bound({ start,end }); it1--; if (it1 == interval.begin()) { new_start = 0; } else { if (it1->second + 1 == start) { new_start = it1->first; //empty_space.erase(*it1); //interval.erase(*it1); } else { new_start = start; } } if (it2 == interval.end()) { new_end = n - 1; } else { if (it2->first - 1 == end) { new_end = it2->second; //empty_space.erase(*it2); //interval.erase(*it2); } else { new_end = end; } } empty_space.erase(*it1); interval.erase(*it1); empty_space.erase(*it2); interval.erase(*it2); empty_space.insert({ new_start,new_end }); interval.insert({ new_start,new_end }); return length; } else { return -1; } } /* #ifndef _CRT_SECURE_NO_WARNINGS #define _CRT_SECURE_NO_WARNINGS #endif #include <stdio.h> //#include <iostream> //using namespace std; extern void init(int N); extern int build(int mLength); extern int demolish(int mAddr); #define CMD_INIT 1 #define CMD_BUILD 2 #define CMD_DEMOLISH 3 static bool run() { int query_num; scanf("%d", &query_num); int ans; bool ok = false; for (int q = 0; q < query_num; q++) { int query; scanf("%d", &query); if (query == CMD_INIT) { int N; scanf("%d", &N); init(N); ok = true; } else if (query == CMD_BUILD) { int mLength; scanf("%d", &mLength); int ret = build(mLength); scanf("%d", &ans); if (ans != ret) { //cout<<"Ret: "<<ret<<" "<<ans<<endl; ok = false; } } else if (query == CMD_DEMOLISH) { int mAddr; scanf("%d", &mAddr); int ret = demolish(mAddr); scanf("%d", &ans); if (ans != ret) { ok = false; } } } return ok; } int main() { setbuf(stdout, NULL); freopen("sample_input.txt", "r", stdin); int T, MARK; scanf("%d %d", &T, &MARK); for (int tc = 1; tc <= T; tc++) { int score = run() ? MARK : 0; printf("#%d %d\n", tc, score); } return 0; } 1 100 20 1 30 2 7 11 2 5 21 2 11 0 2 4 26 2 3 18 2 5 -1 3 0 11 2 10 0 3 11 7 3 21 5 3 18 3 3 18 -1 3 2 -1 2 8 14 2 3 10 2 5 -1 3 10 3 3 26 4 3 10 -1 */
Editor is loading...
Leave a Comment