QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#684761 | #5110. Splitstream | iambotx11 | TL | 0ms | 3540kb | C++14 | 2.9kb | 2024-10-28 15:40:56 | 2024-10-28 15:40:57 |
Judging History
answer
#include<iostream>
#include<string.h>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;
struct Node{
string name;
int vId1;
int vId2;
int vId3;
};
struct Dnode{
vector<int> vec;
};
int main(){
int m,n,q;
//cout << "Enter values of m, n and q: " << endl;
cin >> m >> n >> q;
vector<Node> node(n);
vector<pair<int, int>> query(q);
int maxx=1;
for(int i=0;i<n;i++){
//cout << "Enter details of Node " << i+1 << endl;
cin >> node[i].name >> node[i].vId1 >> node[i].vId2 >> node[i].vId3;
maxx=max({maxx, node[i].vId1 , node[i].vId2 , node[i].vId3 });
}
for(int i=0;i<q;i++){
//cout << "Enter details of query " << i+1 << endl;
cin >> query[i].first >> query[i].second;
}
vector<Dnode> vecID(maxx);
//initialize vector with vId1
for(int i=1;i<=m;i++){
vecID[0].vec.push_back(i);
}
vector<int> queue;
queue.push_back(1);
//for processing node calculations
while(queue.size()!=0){
for(int i=0;i<n;i++){
if(node[i].name=="S"){
if(node[i].vId1==queue[0]){
int a=0;
vector<int> v1=vecID[node[i].vId1-1].vec;
vector<int> v2=vecID[node[i].vId2-1].vec;
vector<int> v3=vecID[node[i].vId3-1].vec;
//splitting the input vector
while (a<v1.size()){
if(a<v1.size()) v2.push_back(v1[a++]);
if(a<v1.size()) v3.push_back(v1[a++]);
}
vecID[node[i].vId2-1].vec=v2;
vecID[node[i].vId3-1].vec=v3;
queue.push_back(node[i].vId2);
queue.push_back(node[i].vId3);
node.erase(node.begin()+i);
n--;
break;
}
}
else{
if(node[i].vId1==queue[0] || node[i].vId2==queue[0]){
vector<int> v1=vecID[node[i].vId1-1].vec;
vector<int> v2=vecID[node[i].vId2-1].vec;
vector<int> v3=vecID[node[i].vId3-1].vec;
if(v1.empty() || v2.empty()){
queue.push_back(queue[0]);
break;
}
int ind1=0;
int ind2=0;
while(ind1<v1.size() && ind2<v2.size()){
v3.push_back(v1[ind1++]);
v3.push_back(v2[ind2++]);
}
while(ind1<v1.size()){
v3.push_back(v1[ind1++]);
}
while(ind2<v2.size()){
v3.push_back(v2[ind2++]);
}
vecID[node[i].vId3-1].vec=v3;
queue.push_back(node[i].vId3);
node.erase(node.begin()+i);
n--;
break;
}
}
}
queue.erase(queue.begin());
}
//for processing query
//cout << endl;
//cout << "Output" << endl;
for(int i=0;i<q;i++){
int id = query[i].first - 1;
int pos = query[i].second - 1;
if (id < maxx && pos < vecID[id].vec.size()) {
cout << vecID[id].vec[pos] << endl;
} else {
cout << "none" << endl;
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3540kb
input:
5 8 26 M 8 9 13 S 2 4 5 S 1 2 3 M 6 5 8 S 4 9 10 S 10 14 15 S 3 6 7 S 7 11 12 2 3 2 4 3 2 3 3 4 2 4 3 5 1 5 2 6 1 6 2 7 1 7 2 8 2 8 3 9 1 9 2 10 1 10 2 11 1 11 2 12 1 13 3 13 4 14 1 14 2 15 1
output:
5 none 4 none 5 none 3 none 2 none 4 none 3 none 1 none 5 none 4 none none 3 none 5 none none
result:
ok 26 lines
Test #2:
score: -100
Time Limit Exceeded
input:
1000000000 8191 1000 S 1 2 3 S 2 4 5 S 3 6 7 S 4 8 9 S 5 10 11 S 6 12 13 S 7 14 15 S 8 16 17 S 9 18 19 S 10 20 21 S 11 22 23 S 12 24 25 S 13 26 27 S 14 28 29 S 15 30 31 S 16 32 33 S 17 34 35 S 18 36 37 S 19 38 39 S 20 40 41 S 21 42 43 S 22 44 45 S 23 46 47 S 24 48 49 S 25 50 51 S 26 52 53 S 27 54 55...