QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#618826#7815. 结构体tiankonguse15 0ms4128kbC++205.6kb2024-10-07 10:44:152024-10-07 10:44:16

Judging History

你现在查看的是最新测评结果

  • [2024-10-07 10:44:16]
  • 评测
  • 测评结果:15
  • 用时:0ms
  • 内存:4128kb
  • [2024-10-07 10:44:15]
  • 提交

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 的偏移量
        if (query_type->childs.size() == 0) {
          printf("ERR\n");
          break;
        }
        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: 0ms
memory: 4104kb

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: 5
Accepted
time: 0ms
memory: 4108kb

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:

ERR
ERR
0
8
16
0
24
0
fweahddll
ERR
24
ERR
ERR
ERR
32
34
ERR
0
ERR
36
fweahddll
40
ERR
32
44
44
ERR
wwsp
ERR
24
48
48
40
wqcnqxppvg
8
34
0
ERR
34
8
ERR
ERR
dvqu
ERR
36
ERR
ERR
49
32
ERR
50
52
wwsp
56
erhxh
yuoquzsyr
ERR
0
ERR
24
24
64
72
56
74
32
teuwwrw
80
40
ERR
ERR
80
zuwd
88
teuwwrw
34
96
80
104...

result:

ok 100 lines

Test #3:

score: 5
Accepted
time: 0ms
memory: 4072kb

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: 4128kb

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: 3808kb

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: 3832kb

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: 4124kb

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: 3828kb

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: 3828kb

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: 3780kb

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: 3896kb

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: 3828kb

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: 3844kb

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: 3864kb

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: 3824kb

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: 4108kb

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: 3896kb

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: 3816kb

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: 4084kb

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: 3868kb

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'