QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #618816 | #7815. 结构体 | tiankonguse | 10 | 1ms | 4112kb | C++20 | 5.5kb | 2024-10-07 10:38:32 | 2024-10-07 10:38:33 |
Judging History
answer
/*
ID: tiankonguse
TASK: struct
LANG: C++
CONTEST: CSP-S 2023
qoj: https://qoj.ac/contest/1428/problem/7815
luogu: https://www.luogu.com.cn/problem/P9754
*/
#define TASK "struct"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int debug = 0;
#define myprintf(...) \
do { \
if (debug) printf(__VA_ARGS__); \
} while (0)
void InitIO() {
// #ifndef USACO_LOCAL_JUDGE
// freopen(TASK ".in", "r", stdin);
// freopen(TASK ".out", "w", stdout);
// #endif
}
class Member {
public:
string type;
string name;
ll offset;
Member() { offset = 0; }
Member(const string& type_, const string& name_, ll offset_ = 0)
: type(type_), name(name_), offset(offset_) {}
};
class Type {
public:
bool base_type;
ll type_size;
string name;
vector<Member> childs;
map<string, ll> childName2Index;
map<ll, ll> offset2Index;
Type() : type_size(0) {}
Type(const string& name_, ll type_size_ = 0, bool base_type_ = false)
: name(name_), type_size(type_size_), base_type(base_type_) {}
Member* AddMember(const string& type_, const string& name_, ll offset_ = 0) {
myprintf("Type[%s] add member: type[%s] name[%s] offset[%lld]\n",
name.c_str(), type_.c_str(), name_.c_str(), offset_);
this->childs.emplace_back(std::move(Member(type_, name_, offset_)));
this->childName2Index[name_] = childs.size() - 1;
return &this->childs.back();
}
Member* GetMember(const string& name_) {
if (!childName2Index.count(name_)) return nullptr;
return &childs[childName2Index[name_]];
}
ll GetChildNum() { return childs.size(); }
};
vector<Type> types;
map<string, int> typeName2Index;
Type global;
ll offset = 0;
Type* GetType(const string& name) {
if (!typeName2Index.count(name)) return nullptr;
return &types[typeName2Index[name]];
}
Type* AddType(const string& name, ll type_size = 0, bool base_type_ = false) {
types.emplace_back(std::move(Type(name, type_size, base_type_)));
typeName2Index[name] = types.size() - 1;
return &types.back();
}
void Init() {
AddType("byte", 1, true);
AddType("short", 2, true);
AddType("int", 4, true);
AddType("long", 8, true);
global.name = "Global";
global.type_size = -1;
}
void Solver() { //
Init();
ll n;
scanf("%lld", &n);
while (n--) {
int op;
scanf("%d", &op);
if (op == 1) {
char str[20], type[20], name[20];
int k;
scanf("%s%lld", &str, &k);
Type* t = AddType(str);
ll max_child_size = 0;
for (int i = 0; i < k; i++) {
scanf("%s%s", type, name);
t->AddMember(type, name);
max_child_size = max(max_child_size, GetType(type)->type_size);
}
t->type_size = k * max_child_size;
for (int i = 0; i < k; i++) {
ll offset = i * max_child_size;
t->childs[i].offset = i * max_child_size;
t->offset2Index[offset] = i;
}
printf("%lld %lld\n", t->type_size, max_child_size);
} else if (op == 2) {
char type[20], name[20];
scanf("%s%s", type, name);
const Type* t = GetType(type);
ll type_size = t->type_size;
offset = (offset + type_size - 1) / type_size * type_size;
global.AddMember(type, name, offset);
global.offset2Index[offset] = global.GetChildNum() - 1;
printf("%lld\n", offset);
offset += type_size;
} else if (op == 3) {
getchar(); // skip space
string name;
Type* query_type = &global;
ll query_offset = 0;
while (true) {
char c = getchar();
if ('a' <= c && c <= 'z') {
name.push_back(c);
} else {
myprintf("step typeName[%s] typeSize[%lld] from[%lld] name[%s]\n",
query_type->name.c_str(), query_type->type_size, query_offset,
name.c_str());
const Member* childMember = query_type->GetMember(name);
query_offset += childMember->offset;
query_type = GetType(childMember->type);
myprintf("->to[%lld] childType[%s] ChidName[%s]\n", query_offset,
childMember->type.c_str(), name.c_str());
name.clear();
if (c != '.') {
break;
}
}
}
printf("%lld\n", query_offset);
} else {
ll query_offset = 0;
scanf("%lld", &query_offset);
const Type* query_type = &global;
string path;
while (true) { // query_offset 已修正，代表 query_type 的偏移量
auto it = query_type->offset2Index.upper_bound(query_offset);
it--; //
const ll childIndex = it->second;
const Member& member = query_type->childs[childIndex];
const ll child_offset = member.offset;
const std::string& child_name = member.name;
const Type* child_type = GetType(member.type);
if (query_offset >= child_offset + child_type->type_size) { // 在空洞
printf("ERR\n");
break;
}
path.append(child_name);
query_offset -= child_offset;
query_type = child_type;
if (query_type->base_type) {
printf("%s\n", path.c_str());
break;
}
path.push_back('.');
}
}
}
}
int main() {
InitIO();
Solver();
return 0;
}
/*
5
1 a 2
short aa
int ab
1 b 2
a ba
long bb
2 b x
3 x.ba.ab
4 10
8 4
16 8
0
4
x.bb
*/
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 5
Accepted
time: 1ms
memory: 3848kb
input:
93 2 long gkwc 3 gkwc 2 long omvjdthb 4 1 2 long cumx 3 omvjdthb 4 16 3 gkwc 2 long tebdginn 4 15 4 30 3 omvjdthb 4 22 4 37 2 long nbghbbahln 2 long kkjzl 4 9 3 nbghbbahln 4 31 3 nbghbbahln 3 gkwc 2 long hjzfa 2 long tptemwur 4 39 3 tptemwur 2 long sjybn 4 8 4 15 3 cumx 2 long xathyrnc 4 32 3 xathyr...
output:
0 0 8 gkwc 16 8 cumx 0 24 omvjdthb tebdginn 8 cumx ERR 32 40 omvjdthb 32 tebdginn 32 0 48 56 nbghbbahln 56 64 omvjdthb omvjdthb 16 72 nbghbbahln 72 72 80 88 ERR cumx hjzfa 32 8 16 omvjdthb ERR 96 104 omvjdthb 64 96 cumx 8 112 120 tptemwur 128 136 144 cumx 48 88 152 sjybn 144 48 16 80 gkwc 96 tptemwu...
result:
ok 93 lines
Test #2:
score: 0
Runtime Error
input:
100 4 0 4 4 2 byte szqir 2 long fweahddll 2 byte dvqu 3 szqir 2 long wqcnqxppvg 3 szqir 4 9 4 33 3 wqcnqxppvg 4 38 4 5 4 33 2 short erhxh 2 short wwsp 4 3 3 szqir 4 42 2 short pxkwnp 4 15 2 int teuwwrw 4 45 3 erhxh 2 int uuycypz 3 uuycypz 4 48 4 35 4 6 3 wqcnqxppvg 2 byte yvgc 3 yvgc 3 teuwwrw 4 25 ...
output:
result:
Test #3:
score: 5
Accepted
time: 0ms
memory: 3788kb
input:
99 2 long mrbfn 4 1 3 mrbfn 3 mrbfn 3 mrbfn 3 mrbfn 2 byte oosmberlsb 3 mrbfn 3 oosmberlsb 2 byte auhmoewi 4 7 4 3 2 long jplopgx 4 0 4 31 2 int qqgjpu 2 long plfawkhtd 3 auhmoewi 3 plfawkhtd 2 int uwue 2 long muvlnlgqn 4 46 4 46 4 22 2 long inhosie 3 auhmoewi 3 oosmberlsb 2 byte pziz 2 byte anyxdru...
output:
0 mrbfn 0 0 0 0 8 0 8 9 mrbfn mrbfn 16 mrbfn ERR 24 32 9 32 40 48 ERR ERR jplopgx 56 9 8 64 65 ERR 56 mrbfn plfawkhtd plfawkhtd ERR ERR 66 72 80 56 88 0 24 80 80 inhosie ERR 96 64 104 112 66 120 104 120 128 0 ERR 9 136 144 145 152 65 160 anyxdruw 164 ERR 168 72 170 wbpatry 152 48 cjzosekh cbnapeqnwr...
result:
ok 99 lines
Test #4:
score: 0
Wrong Answer
time: 0ms
memory: 3800kb
input:
99 1 lfqikjtpgg 97 long mbtn long snpj long fqb long vdnkbv long zqqjxhrj long upp long oe long lv long sea long a long fdymaqnuy long oyshjkhm long secuap long o long uvq long xpw long fsytmbpaaw long rx long nhmski long hzop long noy long mqbitjlx long jewquyks long auntk long ak long bsksgoi long...
output:
776 8
result:
wrong answer 2nd lines differ - expected: '0', found: ''
Test #5:
score: 0
Wrong Answer
time: 0ms
memory: 3828kb
input:
92 1 stmyil 94 long frzkeaq long uloz long khxrakhvl long mgmigozwpb long gcmzgib long tktaj long ttgattk long ugnfjyqjei long qqihkphedp long jps long bhdunqh long qsefx long iujkjmuolx long lpyffp long qryknjg long utrepva long dsmu long qxazh long nc long u long lzslpheclz long ftjm long chwf lon...
output:
752 8
result:
wrong answer 2nd lines differ - expected: '0', found: ''
Test #6:
score: 0
Wrong Answer
time: 0ms
memory: 3828kb
input:
98 1 mmozfzqkeq 98 byte snth short p short ukfuxuar byte vidqzvet short mtzfq byte umfo short rxzppsvp short jkcngxzj byte upvqni short wnthhncby byte zzwunbs short hsmgblo short ccgvhtx byte wmru byte gfhcr short fwfanwrr byte wyhihbma byte rppirq short nspggyr short wkntvbwwlv byte hoqqz byte fvcn...
output:
196 2
result:
wrong answer 1st lines differ - expected: '162 2', found: '196 2'
Test #7:
score: 0
Wrong Answer
time: 0ms
memory: 3824kb
input:
92 1 xreiqsyjsl 94 int joqtxmb byte eobzfc int yglime int ghhoizgeq long kiza long aef int ahkehlz byte kgzpv long nf byte hmshwxalu short tniregati byte m short ybauqfo byte tmtnxog int etgavrbmqj short mdirp int qofuzp int lzyvpl int tfdwv int obskuccugg byte bgq short ze long bpyzngywya int rcyis...
output:
752 8
result:
wrong answer 1st lines differ - expected: '496 8', found: '752 8'
Test #8:
score: 0
Wrong Answer
time: 0ms
memory: 3864kb
input:
93 1 spkif 90 short klz short wlbylhewfp short kyaoz byte iuszpejqeb short hlbbgkvnhn short xwsavtujm byte pgfwluu byte mbsh short ybzxrav short ilmd short dvntuiawh short ucbdcgwkyr short m byte qefbom short rpdiishks short dbq byte amiipjf short rcuw byte ct short brdieyded short snuehuwrbf byte o...
output:
180 2
result:
wrong answer 1st lines differ - expected: '164 2', found: '180 2'
Test #9:
score: 0
Wrong Answer
time: 0ms
memory: 3824kb
input:
100 1 tmwddcqr 96 long vc long bzjxjo long rpfgxjw long rwfnwjxezo long evovfc long gj long zwoml long qtgongwrsf long qoti long xoisdmvl long vkcbsjti long lyv long ipjvh long lmemkym long zybinjoacb long xo long opaxv long fd long cheprbq long vwmixkoa long qkxjkn long ty long ad long nrrm long kl...
output:
768 8
result:
wrong answer 2nd lines differ - expected: '800 8', found: ''
Test #10:
score: 0
Wrong Answer
time: 0ms
memory: 3840kb
input:
94 1 oeareonbmc 94 long sjlbu long ddjtxqy long ac long rjmwvryp long bjw long kjxs long dns long wycl long scucpcfki long vhotgxwf long yfgvgw long xb long um long cmcuihmv long jwyuguj long dl long hgecyw long cn long xrwhhsqoar long xfajrvvuy long pg long ln long bwgziqt long knwn long mjmz long ...
output:
752 8
result:
wrong answer 2nd lines differ - expected: '776 8', found: ''
Test #11:
score: 0
Wrong Answer
time: 0ms
memory: 3800kb
input:
100 1 qg 75 short imvphecx long tgthzzocgy int z long rdkrbwqi long bkzeqx byte ebcxwfjeka long ugvjxbayyc int srjda long ah short nhqbw int twpca byte hynzjak long mwrjaitjf byte qeensxo short oc int pniisvwlr int yvqoaipq long nwokprd long pryksxsjti byte zhbuomugxl int bgk byte luo byte kmimxmj b...
output:
600 8
result:
wrong answer 1st lines differ - expected: '368 8', found: '600 8'
Test #12:
score: 0
Wrong Answer
time: 0ms
memory: 4112kb
input:
98 1 prjerge 52 short baiklk short pdauxtmhcs long bmutcn long xhrktulr short gxqgh short ylxevjych short rgd byte gixpucez int bbmq byte giezc short goonshi byte pupsmxs int jmadko byte lziz short azfctnm long pxlp int lcezuwix int pwcmndzare int isjkucax int tngygloe int vjcs int dbcsddgz short ct...
output:
416 8
result:
wrong answer 1st lines differ - expected: '240 8', found: '416 8'
Test #13:
score: 0
Wrong Answer
time: 0ms
memory: 3800kb
input:
95 1 icyrswqfl 93 short qffx byte lkojhr long hhsbxdps long gcsi long hiznsou short hjwpmzywv int hhxyuk byte vrudbiwl byte cqmcxfx long jzdrah int uafucqu int gwixgsyfa short ezyti long iczdyjxa short tc short vyvozoirs long m int kpmg short ecxfhjhfu short gwdqiiza int yfjmrewujt int hl long t lon...
output:
744 8
result:
wrong answer 1st lines differ - expected: '472 8', found: '744 8'
Test #14:
score: 0
Wrong Answer
time: 0ms
memory: 3832kb
input:
93 1 rrcruvb 100 long gbrpkh long o long npx long fqbwyv long cer long xtmxwgset long slohh long r long kkljaga long wkesor long belhrmxthz long bw long vx long wfqc long nqdvlk long v long mlgm long hioyoss long rhpyhqr long troazjcq long got long mxkp long nwayf long qofxrrhp long ttskfndao long j...
output:
800 8
result:
wrong answer 2nd lines differ - expected: '648 8', found: ''
Test #15:
score: 0
Wrong Answer
time: 0ms
memory: 3816kb
input:
92 1 mfqfaoi 51 long vgiijn long kqvmcutd long kkqmfdmdsg long we long h long lx long bdzy long tqb long ayybs long iefznflod long qjw long xq long hajgbfpuqj long otlrrbqpy long xpxyro long lum long umizkapzp long jxjjgsuab long aesd long redlyai long htpfoi long eyo long hkc long hb long wwt long ...
output:
408 8
result:
wrong answer 2nd lines differ - expected: '512 8', found: ''
Test #16:
score: 0
Wrong Answer
time: 0ms
memory: 3824kb
input:
92 1 itmex 54 long qlmtjv long eoiw long ef long imfhgcc long cvvwlhqj long pwrrrcarid long ejs long v long cjl long qfhsxdx long opqhk long rtyfmpb long cgefjpnsyj long oaovfhc long vun long thwqf long hhdrhsizr long ckwl long gaxdzp long mwcw long knjp long zcemzmfs long zlnjmriio long oein long s...
output:
432 8
result:
wrong answer 2nd lines differ - expected: '696 8', found: ''
Test #17:
score: 0
Wrong Answer
time: 0ms
memory: 3828kb
input:
94 1 gzvgm 96 int ozzmlzdcs short lzf int tc int cpagll byte jktmts long qtsyn long rfyehp int dmfpk byte dourj byte aoqijd short er int aykwg byte bozawefpt short kodpn short lk byte xxem byte cvo long vdowzxhn short rutrrcfua short wev short wnkufo byte hvo int ovnbmuq long rcx short ngtdtdxt byte...
output:
768 8
result:
wrong answer 1st lines differ - expected: '400 8', found: '768 8'
Test #18:
score: 0
Wrong Answer
time: 0ms
memory: 3796kb
input:
92 1 pyrj 59 short qjazriblv int udo long ifisemk int inso byte lpmnuevtab int ilrtum byte aucf byte qvwxbxcevi long sxboxvu byte rjfpvq byte iteamtvj int lrsf short nnbnd long ndiwpi short hvcpdhh short rqmusonxma short agoriisqdu short jqskvkw short qyq long zvmpxd byte mbb long kpabhzk int qktde ...
output:
472 8
result:
wrong answer 1st lines differ - expected: '280 8', found: '472 8'
Test #19:
score: 0
Wrong Answer
time: 0ms
memory: 4088kb
input:
100 1 deam 92 int puxuhin byte qzbt byte oelfvt short qjhpt short zvmv byte hmdzptx long mctwgosxff short uygqtcthn long ykshnocnt int ybsvabraeu int qzwh long brrtu byte fide byte lisonhykl short pmsend byte dhqyw short rso long vmuhoz byte kasnh long lyjjfblrb short uzsagojr byte odqcqtjcvs byte m...
output:
736 8
result:
wrong answer 1st lines differ - expected: '408 8', found: '736 8'
Test #20:
score: 0
Wrong Answer
time: 0ms
memory: 4088kb
input:
100 1 vmtrvlmprp 99 byte hbvh long ifeouvbu long ylh long hqgw int wcs short oavgeme byte ppmssx byte prdykjzgw byte obta short yzf byte ozqfbozj short vuypsqhd byte anwbcc byte iiungtbs short dkhape byte ixh short gbdm long ijrczrv short rgkc short amskm short jguttrfv short dotlif byte tqvwccaafx ...
output:
792 8
result:
wrong answer 1st lines differ - expected: '440 8', found: '792 8'