本人tigerzoos,tiger2005因为跳这个代码疯了,所以换上我发求助。
情况是RE了好几次,用的是vector所以不用太关系内存问题。
Code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<string>
#include<iostream>
using namespace std;
int T;
struct Info{
int info_num;
string info_str;
bool is_num;
bool operator > (Info a){
if(is_num) return info_num>a.info_num;
return info_str>a.info_str;
}
bool operator <(Info a){return a>(*this);}
bool operator >=(Info a){return !((*this)<a);}
bool operator <=(Info a){return !((*this)>a);}
bool operator !=(Info a){return ((*this)>a) ^ (a>(*this));}
Info(bool is_num):is_num(is_num){
info_num=0;
info_str="";
}
bool operator == (Info a){
return a.info_num==info_num && a.info_str==info_str && a.is_num==is_num;
}
void init(){
if(is_num) cin >> info_num;
else cin >> info_str;
}
void print(){
if(is_num) cout << info_num;
else cout << info_str;
}
};
vector<Info> empty_vec;
struct Matrix{
string name;
int length,width;
vector<string> sum_str;
vector<char> sum_typ;
vector<vector<Info> > info;
map<string,int> GetColumnByName;
Matrix(){
name="";
length=width=0;
info.clear();
}
}emp_mat;
vector<Matrix> SQL;
map<string,Matrix> GetMatrixByName;
int N;
vector<vector<string> > Query;
vector<string> Command;
vector<string> ColumnList;
Matrix ChosenMatrix;
vector<bool> ChosenRow;
vector<string> empty_str;
vector<int> BracketMatch;
bool add;
int add_num;
int getNum(string str,int st){
int num=0;int flag=1;
while(str[st]=='+' || str[st]=='-'){
flag*=(str[st]=='+'?1:-1);
++st;
}
while(isdigit(str[st])){
num=num*10+(str[st]-'0');
++st;
}
return num*flag;
}
string Transfer(string str){
string ret="";
for(int i=0;str[i];i++){
if(str[i]=='\\') ++i;
ret+=str[i];
}
return ret;
}
bool CalcLogicAnswer(int,int,int);
bool CalcSingleQuestion(int l,int r,int RowID){
int tim=0;
while(Command[l]=="NOT") ++tim,++l;
if(Command[l]=="(") return CalcLogicAnswer(l+1,r-1,RowID);
Info LHS(0),RHS(0);
if(Command[l]=="\"" || Command[l]=="\'"){
LHS.is_num=false;
if(Command[l+1]!="\"" && Command[l+1]!="\'"){
LHS.info_str=Transfer(Command[l+1]);++l;
}
l+=2;
}
else if(isdigit(Command[l][0])){
LHS.is_num=true;
LHS.info_num=getNum(Command[l],0);
++l;
}
else{
LHS=ChosenMatrix.info[RowID][ChosenMatrix.GetColumnByName[Command[l]]];
++l;
}
string Oper=Command[l];++l;
if(Command[l]=="\"" || Command[l]=="\'"){
RHS.is_num=false;
if(Command[l+1]!="\"" && Command[l+1]!="\'"){
RHS.info_str=Command[l+1];++l;
}
l+=2;
}
else if(isdigit(Command[l][0])){
RHS.is_num=true;
RHS.info_num=getNum(Command[l],0);
++l;
}
else{
RHS=ChosenMatrix.info[RowID][ChosenMatrix.GetColumnByName[Command[l]]];
++l;
}
bool ret;
if(Oper=="=") ret=LHS==RHS;
if(Oper==">") ret=LHS>RHS;
if(Oper=="<") ret=LHS<RHS;
if(Oper==">=") ret=LHS>=RHS;
if(Oper=="<=") ret=LHS<=RHS;
if(Oper=="<>") ret=LHS!=RHS;
if(tim & 1) ret=!ret;
return ret;
}
bool CalcLogicAnswer(int l,int r,int RowID){
bool Ret=true;
bool isAnd=true;
int las=l;
for(int p=l;p<=r;p++){
if(Command[p]=="(") p=BracketMatch[p];
else if(Command[p]=="AND" || Command[p]=="OR"){
bool getRes=CalcSingleQuestion(las,p-1,RowID);
if(isAnd) Ret&=getRes;
else Ret|=getRes;
isAnd=(Command[p]=="AND");
las=p+1;
}
}
bool getRes=CalcSingleQuestion(las,r,RowID);
if(isAnd) Ret&=getRes;
else Ret|=getRes;
return Ret;
}
int OrderL,OrderR;
bool OrderRule(const vector<Info> & a,const vector<Info> & b){
int p=OrderL;
while(p<=OrderR){
Info LHS=a[ChosenMatrix.GetColumnByName[Command[p]]];
Info RHS=b[ChosenMatrix.GetColumnByName[Command[p]]];
if(p<OrderR && Command[p+1]=="ASCENDING"){
if(LHS!=RHS) return LHS<RHS;
p+=2;
}
else if(p<OrderR && Command[p+1]=="DESCENDING"){
if(LHS!=RHS) return LHS>RHS;
p+=2;
}
else{
if(LHS!=RHS) return LHS<RHS;
++p;
}
}
return false;
}
Matrix RunFromStat(int l,int r){
if(BracketMatch[l]==r) return RunFromStat(l+1,r-1);
Matrix ReturnMatrix;
if(Command[l]=="("){
ReturnMatrix=RunFromStat(l,BracketMatch[l]);
l=BracketMatch[l]+1;
}
else{
ReturnMatrix=GetMatrixByName[Command[l]];
++l;
}
if(Command[l]=="INNER"){
l+=2;
Matrix AddedMatrix;
if(Command[l]=="("){
AddedMatrix=RunFromStat(l,BracketMatch[l]);
l=BracketMatch[l]+2;
}
else{
AddedMatrix=GetMatrixByName[Command[l]];
l+=2;
}
Matrix NewMatrix=ReturnMatrix;
NewMatrix.info.clear();
NewMatrix.length=0;
NewMatrix.width+=AddedMatrix.width;
for(int i=0;i<AddedMatrix.sum_str.size();i++)
NewMatrix.sum_str.push_back(AddedMatrix.sum_str[i]);
for(int i=0;i<AddedMatrix.sum_typ.size();i++)
NewMatrix.sum_typ.push_back(AddedMatrix.sum_typ[i]);
for(int i=0;i<NewMatrix.sum_str.size();i++)
NewMatrix.GetColumnByName[NewMatrix.sum_str[i]]=i;
int lx=NewMatrix.GetColumnByName[Command[l]];
int ly=NewMatrix.GetColumnByName[Command[l+2]];
for(int i=0;i<ReturnMatrix.length;i++)
for(int j=0;j<AddedMatrix.length;j++){
Info s1(false),s2(false);
if(lx<ReturnMatrix.width) s1=ReturnMatrix.info[i][lx];
else s1=AddedMatrix.info[j][lx-ReturnMatrix.width];
if(ly<ReturnMatrix.width) s2=ReturnMatrix.info[i][ly];
else s2=AddedMatrix.info[j][ly-ReturnMatrix.width];
if(s1==s2){
NewMatrix.info.push_back(empty_vec);
for(int p=0;p<ReturnMatrix.width;p++)
NewMatrix.info.back().push_back(ReturnMatrix.info[i][p]);
for(int p=0;p<AddedMatrix.width;p++)
NewMatrix.info.back().push_back(AddedMatrix.info[j][p]);
++NewMatrix.length;
}
}
ReturnMatrix=NewMatrix;
}
return ReturnMatrix;
}
int main(){
cin >> T;
while(T--){
SQL.clear();
Query.clear();
Command.clear();
ColumnList.clear();
ChosenMatrix=emp_mat;
ChosenRow.clear();
BracketMatch.clear();
if(!add) cin >> skipws >> N;
else{
N=add_num;
char c;
cin >> noskipws >> c;
while(c>='0' && c<='9'){
N=N*10+c-'0';
cin >> noskipws >> c;
}
add=false;
}
for(int i=0;i<N;i++){
SQL.push_back(emp_mat);
cin >> skipws >> SQL.back().name;
cin >> SQL.back().width;
cin >> SQL.back().length;
for(int j=0;j<SQL.back().width;j++){
SQL.back().sum_str.push_back("");
SQL.back().sum_typ.push_back('\0');
cin >> SQL.back().sum_str.back();
cin >> SQL.back().sum_typ.back();
SQL.back().GetColumnByName[SQL.back().sum_str.back()]=j;
}
for(int j=0;j<SQL.back().length;j++){
SQL.back().info.push_back(empty_vec);
for(int k=0;k<SQL.back().width;k++){
SQL.back().info.back().push_back(Info(
SQL.back().sum_typ[k]=='I'));
SQL.back().info.back().back().init();
}
}
GetMatrixByName[SQL.back().name]=SQL.back();
/*
for(int j=0;j<SQL.back().length;j++){
for(int k=0;k<SQL.back().width;k++){
SQL.back().info[j][k].print();
printf(" ");
}
printf("\n");
}
*/
}
string qwq="";
Query.push_back(empty_str);
bool blank=true;
int typ=0;
while(1){
char c;
if(!(cin >> noskipws >> c)) break;
if(c==','){
if(qwq=="") continue;
Query.back().push_back(qwq);
qwq="";
}
else if((c>='a' && c<='z') || (c>='A' && c<='Z') || (c>='0' && c<='9')){
if(c>='0' && c<='9' && blank){
add=true;
add_num=c-'0';
break;
}
if(typ==2){
Query.back().push_back(qwq);
qwq="";
}
if(blank)
Query.push_back(empty_str);
typ=1;
qwq+=c;blank=false;
}
else if(c==' ' || c=='\n' || c=='\r' || c=='\t'){
if(qwq!="") Query.back().push_back(qwq);
qwq="";
if(c=='\r' || c=='\n') blank=true;
typ=0;
}
else{
if(typ==1 || ((c=='\"' || c=='\'') && qwq!="")){
Query.back().push_back(qwq);
qwq="";
}
if(c=='\\'){
qwq+=c;
cin >> noskipws >> c;
if(c=='\\') c='\\';
else if(c=='\'') c='\'';
else if(c=='\"') c='\"';
}
typ=2;
qwq+=c;blank=false;
}
}
/*
for(int i=0;i<Query.size();i++){
cout << "> ";
for(int j=0;j<Query[i].size();j++)
cout << Query[i][j] << " " ;
cout << endl;
}
*/
for(int i=0;i<Query.size();i++)
for(int j=0;j<Query[i].size();j++)
Command.push_back(Query[i][j]);
BracketMatch.clear();
vector<int> Stacker;
Stacker.clear();
for(int i=0,j=Command.size();i<j;i++){
BracketMatch.push_back(0);
if(Command[i]=="(") Stacker.push_back(i);
if(Command[i]==")"){
BracketMatch[Stacker.back()]=i;
Stacker.pop_back();
}
}
int curr=1;
while(Command[curr]!="FROM"){
ColumnList.push_back(Command[curr]);
++curr;
}
++curr;int startFrom=curr;
int v=Command.size();
while(curr<v && Command[curr]!="WHERE" && Command[curr]!="ORDER")
++curr;
ChosenMatrix=RunFromStat(startFrom,curr-1);
ChosenRow.clear();
for(int i=0;i<ChosenMatrix.length;i++)
ChosenRow.push_back(true);
if(Command[curr]=="WHERE"){
curr+=1;int u=curr,v=Command.size();
while(u<v && Command[u]!="ORDER") ++u;
--u;//curr -> u
for(int i=0;i<ChosenMatrix.length;i++){
if(ChosenRow[i]==false) continue;
int u=curr,v=Command.size();
bool CurrentStatus=true;
bool IsAnd=true;
ChosenRow[i]=CalcLogicAnswer(curr,u,i);
}
curr=u+1;
}
vector<vector<Info> > Library=ChosenMatrix.info;
ChosenMatrix.info.clear();
for(int i=0;i<ChosenMatrix.length;i++)
if(ChosenRow[i]) ChosenMatrix.info.push_back(Library[i]);
ChosenMatrix.length=ChosenMatrix.info.size();
if(Command[curr]=="ORDER"){
curr+=2;
int v=Command.size()-1;
OrderL=curr;
OrderR=v;
sort(ChosenMatrix.info.begin(),ChosenMatrix.info.end(),OrderRule);
}
vector<int> OutputOrder;
OutputOrder.clear();
if(ColumnList[0]=="*")
for(int i=0;i<ChosenMatrix.width;i++)
OutputOrder.push_back(i);
else
for(int i=0;i<ColumnList.size();i++)
OutputOrder.push_back(ChosenMatrix.GetColumnByName[ColumnList[i]]);
cout << OutputOrder.size() << " " << ChosenMatrix.length << endl;
for(int i=0;i<OutputOrder.size();i++)
cout << ChosenMatrix.sum_str[OutputOrder[i]] << endl;
for(int i=0;i<ChosenMatrix.length;i++){
for(int j=0;j<OutputOrder.size();j++){
ChosenMatrix.info[i][OutputOrder[j]].print();
cout << " ";
}
cout << endl;
}
if(T!=0) cout << endl;
}
return 0;
}